Re: once quasi asked about unions of sets ...

In article <obgud3dd3ruj7gmnfi8c7ac0a2313vek7f@xxxxxxx> quasi@xxxxxxxx writes:
On Wed, 05 Sep 2007 11:25:01 EDT, tommy1729 <tommy1729@xxxxxxxxx>
wrote:

quasi once asked if the set Poly_1 U Poly_2 can be given by Poly_3.

it was asked in another tread concerning "deny".

the answer is probably yes

I think the answer is "no". In other words, the union of two
polynomial ranges is not necessarily a polynomial range.

A trivial example is this one ...

Let f(x) = 2x + 1 and g(x) = 2.

Then range(f) is all odd integers and range(g) = {2}.

Suppose range(f) U range(g) = range(h).

Then h is a nonconstant polynomial (with integer coefficients) which
assumes only one even value. It's easy to show that's impossible.

If we require the polynomials be nonconstant, then a counterexample is
not so obvious, and yet, it's still seems likely that there is a
counterexample.

As a specific test case, let f(x) = 2x and g(x) = 3x. Although I don't
see an immediate proof, I'm fairly sure that range(f) U range(g) is
not a polynomial range.

I think that is easy to prove. Suppose there is a polynomial that assumes
all values in the ranges of f and g. All polynomials do only increase
after a certain point, before that time they may have some maxima and minima.
Start looking at the new polynomial where it starts to increase only, and
look at the point where it is larger than its largest maximum. The
requirement that it should pass all points that are not 1 mod 6 or 5 mod 6
dictates that the polynomial should not be superlinear (otherwise from
some point it will skip more than one integer at quite a few points). But
it can not be linear either. So there is no such polynomial.
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast