Timeline for Number of real roots of 0,1 polynomial
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28 at 18:39 | comment | added | fedja | @PeterMueller I posted a code (in Asymptote) that finds an explicit polynomial of degree $40m^2$ with $m-1$ roots. With the standard float point precision, I can go only to $m=11$. Beyond that the rounding errors dominate. I wonder if you want to give it a try with arbitrary precision arithmetic. :-) | |
| Feb 17 at 2:15 | comment | added | fedja | @PeterMueller If you are still interested in the problem, I have one more computational request: Let $A_n$ be the family of polynomials $p$ of degree $\le n$ with coefficients $0,1$ such that $p(0)=1$. Define $f_n(t)=\inf_{p\in A_n}\log\max_{[-1+t,-1+2t+\frac 1n]}|p|$, $0\le t\le\frac 14$, say. I would love to see the graph of $f_n$ for not too small $n$. I don't need super-high precision: 10-20% relative error is fine. But I really want to see the general shape. Thanks in advance! | |
| Jan 20 at 22:00 | comment | added | fedja | @PeterMueller I'm a hopeless, patented, and ultimate imbecile: the ratio must be a polynomial with integer coefficients, so the sum of coefficients of $P$ (a.k.a. the number of 1's and the value at $+1$) must be divisible by $(1+1)^m$. That explains everything... Back to roots on $(-1,0)$ now :-) | |
| Jan 20 at 21:32 | comment | added | fedja | @PeterMueller Yeah, all examples of minimal degree I know also have $2^m$ terms. This is rather suggestive but for the life of mine I cannot figure out why :-) | |
| Jan 20 at 21:13 | comment | added | Peter Mueller | One cannot edit comments :-( The binary linear system above should be $\sum_{k=i}^n\binom{k}{i}a_k(-1)^k=0$, of course. | |
| Jan 20 at 21:10 | comment | added | Peter Mueller | ... I use the MIP solvers Gurobi and Copt (both provide a free academic licence). Without further ideas, I won't get beyond $m=7$. In fact, my program still has not decided whether $D(7)=148$ or $149$. However, it found $13$ examples of degree $149$ so far. (Some of them are not palindromic.) They all have exactly $128$ terms! And the unique example for $D(6)=76$ has $64$ terms. | |
| Jan 20 at 21:00 | comment | added | Peter Mueller | @fedja In fact, I first tried this simple approach (possibly the one you did): For $f=\sum a_kx^k$ we get the binary linear system $\sum\binom{k,i}a_k(-1)^k=$, $0\le i\le m-1$. For $m=6$, this got stuck for $n=\rm{deg}(f)$ somewhat below $60$. But this idea works much better: The coefficient vectors of $f$ of the multiples of $(x+1)^m$ are a $\mathbb Z$-module. Using the block Korkine–Zolotarev lattice basis reduction I get a generating set $v_1,\dots,v_r\in\mathbb Z^{n+1}$ with small integer entries. Now solve for integers $x_1,\dots,x_r$ such that each entry of $\sum x_iv_i$ is $0$ or $1$. | |
| Jan 20 at 13:42 | comment | added | fedja | @PeterMueller Interesting. I wonder what algorithm you used. I just mindlessly set it up as a binary linear program and used a standard LP solver, but this allowed me to go up only to 55. Of course, if we decide to restrict the number of zeroes and to impose the palindromic structure, I can get higher, but still not as high as you did :-) | |
| Jan 20 at 9:25 | comment | added | Peter Mueller | @fedja And here an example $A\bar A$ of degree $149$ with $m=7$, again with $1$'s in the majority: $A=110001111110110110111111111111011111111111111110110011111111111111011111111$. | |
| Jan 19 at 18:56 | comment | added | fedja | @PeterMueller Thanks a lot! That gives some (but only some) hope that the growth of $D(m)$ is subexponential. What is also interesting is that most coefficients are 1's with just a few sparse zeroes. I'm not really sure what to make of this observation though... | |
| Jan 19 at 18:48 | comment | added | Peter Mueller | @fedja $D(6)=76$, assumed for $A0\bar A$ where $A=11001101111111111110111111111111110011$. (The leftmost bit corresponds to the constant term in my notation.) | |
| Jan 19 at 16:48 | comment | added | fedja | @PeterMueller I also tried to compute the minimal degree $D(m)$ of a 0,1-polynomial having a root of multiplicity $m$ at $-1$. The results for small $m$ are a bit discouraging: the sequence of degrees for $m=1,\dots,5$ is $1,4,9,20,41$, the same that can be obtained by the trivial degree doubling procedure (change the string $A$ to $AA$ or $A0A$ depending on the parity of the length). However, for $m=5$, we get an admissible string that breaks this pattern: $B\bar B$ where $B=110001111110111111011$ and $\bar B$ is the reflection of $B$. It would be really interesting to see if $D(6)<84$. | |
| Jan 16 at 8:45 | comment | added | Peter Mueller | @DenisIvanov Yes, in both cases. | |
| Jan 16 at 8:09 | comment | added | Denis Ivanov | @PeterMueller, thank you, I see! Is it first appearances? | |
| Jan 16 at 8:01 | comment | added | Peter Mueller | @DenisIvanov This does not hold. The polynomials for $p=50539$ (degree $15$) and $p=6836587$ (degree $22$) have $3$ and $4$ real roots. | |
| Jan 16 at 6:13 | comment | added | Denis Ivanov | @PeterMueller, I've found that if $p$ is prime than it's poly could has only 1 or 2 roots, never 3 or more. Your calculations confirm this? Is there a simple explanation? | |
| Jan 15 at 16:30 | comment | added | Peter Mueller | @fedja With the present exhaustive brute force approach, it will be difficult. All $0,1$-polynomials of degree $\le31$ have at most $3$ roots in $(0, 1)$. Presently the program searches degree $32$, but that may take a while. | |
| Jan 15 at 13:51 | comment | added | fedja | Excellent, thank you! I f you could also do 4 and 5, it would be absolutely great :-) | |
| Jan 15 at 10:07 | comment | added | Peter Mueller | @fedja The minimal degrees for having $1$, $2$ or $3$ roots in $(-1, 0)$ are $3$, $10$, and $21$ with the examples $\{1+x+x^3\}$, $\{1+x+x^3+x^8+x^{10}, 1+x+x^3+x^5+x^6+x^8+x^{10}\}$ and $\{1+x+x^3+x^8+x^{10}+x^{12}+x^{17}+x^{19}+x^{21}, 1+x+x^3+x^6+x^7+x^8+x^{10}+x^{11}+x^{12}+x^{14}+x^{17}+x^{19}+x^{21}, 1+x+x^3+x^8+x^{10}+x^{12}+x^{14}+x^{15}+x^{17}+x^{19}+x^{21}, 1+x+x^3+x^8+x^{10}+x^{12}+x^{15}+x^{16}+x^{17}+x^{19}+x^{21}\}$, respectively. | |
| Jan 15 at 5:29 | comment | added | fedja | It would be also interesting to consider the 0,1-polynomials of minimal degree having the prescribed number of roots on the open interval $(-1,0)$. Can you compute a few of those? | |
| Jan 14 at 15:51 | comment | added | Max Alekseyev |
Pythonic way would be l = [f'x^{j}' for j, b in enumerate(bin(p)[-1:1:-1]) if b == '1']
|
|
| Jan 11 at 21:23 | comment | added | Peter Mueller | @DenisIvanov Indeed, I do not expect that that $p_7$ and $p_8$ are examples with minimal degree. Thus I edited your table, replacing $45(?)$ and $52(?)$ with $\le45$ and $\le52$, respectively. By the way, the present state of the calculation shows $\nu(7)\ge35$. | |
| Jan 11 at 18:06 | comment | added | Denis Ivanov | @PeterMueller, Thank you for cool work! I've got some doubts about $p_7$ 'cause all other polys have $-1$ root (include $p_8$!), but $p_7$ don't | |
| Jan 8 at 16:23 | comment | added | Peter Mueller | @MarcoGolla Yes, I might do that. But I'll wait a little to see if someone produces better results. The present code can go up to degree $31$ within a few hours on $17$ cores. There is some room for optimizations though. But with the present brute force approach, I don't believe that one can go beyond degree $40$. | |
| Jan 8 at 16:17 | history | edited | Peter Mueller | CC BY-SA 4.0 |
simplified program code
|
| Jan 8 at 13:10 | comment | added | Marco Golla | Have you considered sending the data to the OEIS? As mentioned above, the function $\nu$ is closely related to oeis.org/A362344 . | |
| Jan 8 at 11:39 | history | edited | Peter Mueller | CC BY-SA 4.0 |
added 742 characters in body
|
| Jan 7 at 22:54 | history | answered | Peter Mueller | CC BY-SA 4.0 |