16. Dec. 1992, Bielefeld
Discrete Optimization:
Find Polynomials
n
---
\ i n-i
P (x) = > a x (1-x)
n / i
---
i=0
with integer coefficients 0 <= a <= Binomial[n,i]
i
such that P_n(x) is not the identity and has as many as
possible fixpoints in closed interval [0,1].
For n = 1..5 you can get n different fixpoints in the interval [0,1].
p_1 : [1,0] = [a0, a1]
p_2 : [0,0,1] = [a0, a1, a2]
p_3 : [0,3,0,1]
p_4 : [0,0,6,2,1]
p_5 : [0,2,0,10,3,1]
The case n=6 is the first time, where you can get only n-1 different
fixpoints in [0,1].
For n=20 I managed to get 17 fixpoints. Can you beat this?
What are optimalization procedures in this case?
(Simulated Annealing with the neightbourhood 'change one coefficient
a little bit' is no good idea, as almost all fixpoints will be
complex typically.)
You can construct polynomials with 0.2*n fixpoints. Can you find
a better lower bound?
This was a exercise in a 2nd year math course. We recieved one
solution. Three students constructed (4 pages) a polynomial with
fix points at k/(n-1). Then they showed that the coefficients
are integers and in the allowed range. So they constructed
at least n different fixpoints. But they missed that they had
found the identity. They started their induction for n=3.
Torsten Sillke
-------------------------------------------------------------------------
When is P_n the identity?
n
---
\ i n-i
P (x) = > a x (1-x) = x
n / n,i
---
i=0
n
---
\ i n
> a (x/(1-x)) = x / (1-x)
/ n,i
---
i=0
substitute z = x/(1-x) which is x = z/(1+z)
n
---
\ i n-1
> a z = z (z+1)
/ n,i
---
i=0
this gives you:
a = Binomial[ n-1, i-1 ]
n,i
in particular a = 0
n,0
-------------------------------------------------------------------------
It is equivalent:
A) the number of different Fixpoint in [0,1] of the polynomial:
n
---
\ i n-i
P (x) = > p x (1-x)
n / n,i
---
i=0
with integer coefficients: 0 <= p <= Binomial[n,i]
n,i
B) the number of different positive zeroes (0 <= z <= +inf) of the polynomial:
n
---
\ i
Q (z) = > q z
n / n,i
---
i=0
(if q(n,n)=0 you count a zero at +inf.)
with integer coefficients: -Binomial[n-1,i-1] <= q <= Binomial[n-1,i]
n,i
The transformation is:
p = q + Binomial[n-1,i-1]
n,i n,i
and the roots z transform to the fixpoints x as:
x = z/(z+1).
Example: n=20
R20(x) = ((x-1)(x-2)(2x-1)(x^4-8x^3+15x^2-8x+1)
(x x-3x+1)(x x-4x +1)(x^4-7x^3+13x^2-7x+1))
Q20(x) = x x (x+1) R20(x)
---------------------------------------------------------------
Torsten Sillke