Skip to main content
MathOverflow

Return to Question

added 548 characters in body
Source Link
Wolfgang
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

If $A$ is feasible (meaning that all coefficients of $p_A$ are in $\{-1,0,1\}$), it may be a good candidate, as the terms in the middle of the (symmetricpalindromic and unimodal) polynomials $q_A(x)$ can be quite big. I have no idea whether these polynomials are the best possible ones, but you may judge by some examples that they can have factors with quite impressive heights:

$$\begin{align} A=\{2,5,7,8,9\} &\implies f(31)\geqslant 450 \\ A=\{2,6,8,10,13,14\} &\implies f(53)\geqslant 9736\\ A=\{4,7,12, 17,18,19\} &\implies f(77)\geqslant 75552\\ A=\{2, 6, 8, 17, 22, 25, 28\} &\implies f( 108 ) \geqslant 697675. \end{align}$$ EDIT: As per section 6.2.3 of the survey article by J.Abbott quoted in a comment, extensive computer searches quoted in turn from Peter Borwein and Michael J. Mossinghoff, Polynomials with Height 1 and Prescribed Vanishing at 1 have found much better sets, e.g. $$\begin{align} A=\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13\} &\implies f( 69) \geqslant 2930202\\ A=\{1, 2, 3, 5, 6, 7, 8, 9, 11, 11, 13, 17, 19\} &\implies f( 112) \geqslant 1706914952. \end{align}$$

As the number of elements of $A$ grows, it is increasingly difficult to come up with feasible sets which have relatively small elements. A necessary and sufficient (edit: but by now way necessary!) condition for feasibility is that $A$ is "even-sum-free" (e.s.f.), for lack of a better term, meaning that any two subsets of even order have pairwise different sums, and any two subsets of odd order have pairwise different sums. This condition ensures that each power of $x$ occurs at most once in $p_A$, so it is sufficient. To see that it is also necessary, assume $A$ has a pair of (wlog disjoint) subsets of same parity and same sums. Consider one where this sum is maximal. The corresponding coefficient $\pm2$ cannot be compensated by other subsets without producing a coefficient $\pm2$ in a term of higher order, so this set is not feasible.

Note that thosee.s.f. sets have similar features as Sidon sets, a.k.a. Golomb rulers. By the way, if we take the last of the optimal Golomb rulers of order 7, viz. (0 2 7 13 21 22 25), and increase it by 4, it produces a feasible set $$A=\{4, 6, 11, 17, 25, 26, 29\} \implies f( 118 ) \geqslant 2203567.$$ (Maybe I was just lucky here, I didn't play a lot with Golomb rulers.)

It is not hard to see that $f$ grows stronger than any polynomial. In fact, for a given $k$, we can start with a feasible set $A=\{a_1,\dots,a_k\}$ (and such a set exists, e.g. $A=\{2,4,8,\dots,2^k\}$, which is very wasteful but sufficient here) and put $s:=a_1+\cdots+a_k$. Then, to be even more generous, each set $A+ks, A+ks+1,...$ is feasible as well, and the heights of $q_{A+ks+n},n\in\mathbb N,$ are $O(n^k)$.

So A very loose exponential lower bound is given by $f(2^n) \geqslant 2^{\binom{n-1}2}$. Empirically, something like $f(n) \geqslant \exp(n/7)$ seems possible. So the obvious question is:

What would be (maybe at least asymptotically) a goodnot-to-loose lower bound of $f(n)$?

If $A$ is feasible (meaning that all coefficients of $p_A$ are in $\{-1,0,1\}$), it may be a good candidate, as the terms in the middle of the (symmetric and unimodal) polynomials $q_A(x)$ can be quite big. I have no idea whether these polynomials are the best possible ones, but you may judge by some examples that they can have factors with quite impressive heights:

$$\begin{align} A=\{2,5,7,8,9\} &\implies f(31)\geqslant 450 \\ A=\{2,6,8,10,13,14\} &\implies f(53)\geqslant 9736\\ A=\{4,7,12, 17,18,19\} &\implies f(77)\geqslant 75552\\ A=\{2, 6, 8, 17, 22, 25, 28\} &\implies f( 108 ) \geqslant 697675. \end{align}$$

As the number of elements of $A$ grows, it is increasingly difficult to come up with feasible sets which have relatively small elements. A necessary and sufficient condition for feasibility is that $A$ is "even-sum-free" (e.s.f.), for lack of a better term, meaning that any two subsets of even order have pairwise different sums, and any two subsets of odd order have pairwise different sums. This condition ensures that each power of $x$ occurs at most once in $p_A$, so it is sufficient. To see that it is also necessary, assume $A$ has a pair of (wlog disjoint) subsets of same parity and same sums. Consider one where this sum is maximal. The corresponding coefficient $\pm2$ cannot be compensated by other subsets without producing a coefficient $\pm2$ in a term of higher order, so this set is not feasible.

Note that those sets have similar features as Sidon sets, a.k.a. Golomb rulers. By the way, if we take the last of the optimal Golomb rulers of order 7, viz. (0 2 7 13 21 22 25), and increase it by 4, it produces a feasible set $$A=\{4, 6, 11, 17, 25, 26, 29\} \implies f( 118 ) \geqslant 2203567.$$ (Maybe I was just lucky here, I didn't play a lot with Golomb rulers.)

It is not hard to see that $f$ grows stronger than any polynomial. In fact, for a given $k$, we can start with a feasible set $A=\{a_1,\dots,a_k\}$ (and such a set exists, e.g. $A=\{2,4,8,\dots,2^k\}$, which is very wasteful but sufficient here) and put $s:=a_1+\cdots+a_k$. Then, to be even more generous, each set $A+ks, A+ks+1,...$ is feasible as well, and the heights of $q_{A+ks+n},n\in\mathbb N,$ are $O(n^k)$.

So the obvious question is:

What would be (maybe at least asymptotically) a good lower bound of $f(n)$?

If $A$ is feasible (meaning that all coefficients of $p_A$ are in $\{-1,0,1\}$), it may be a good candidate, as the terms in the middle of the (palindromic and unimodal) polynomials $q_A(x)$ can be quite big. I have no idea whether these polynomials are the best possible ones, but you may judge by some examples that they can have factors with quite impressive heights:

$$\begin{align} A=\{2,5,7,8,9\} &\implies f(31)\geqslant 450 \\ A=\{2,6,8,10,13,14\} &\implies f(53)\geqslant 9736\\ A=\{4,7,12, 17,18,19\} &\implies f(77)\geqslant 75552\\ A=\{2, 6, 8, 17, 22, 25, 28\} &\implies f( 108 ) \geqslant 697675. \end{align}$$ EDIT: As per section 6.2.3 of the survey article by J.Abbott quoted in a comment, extensive computer searches quoted in turn from Peter Borwein and Michael J. Mossinghoff, Polynomials with Height 1 and Prescribed Vanishing at 1 have found much better sets, e.g. $$\begin{align} A=\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13\} &\implies f( 69) \geqslant 2930202\\ A=\{1, 2, 3, 5, 6, 7, 8, 9, 11, 11, 13, 17, 19\} &\implies f( 112) \geqslant 1706914952. \end{align}$$

As the number of elements of $A$ grows, it is increasingly difficult to come up with feasible sets which have relatively small elements. A sufficient (edit: but by now way necessary!) condition for feasibility is that $A$ is "even-sum-free" (e.s.f.), for lack of a better term, meaning that any two subsets of even order have pairwise different sums, and any two subsets of odd order have pairwise different sums. This condition ensures that each power of $x$ occurs at most once in $p_A$, so it is sufficient.

Note that e.s.f. sets have similar features as Sidon sets, a.k.a. Golomb rulers. By the way, if we take the last of the optimal Golomb rulers of order 7, viz. (0 2 7 13 21 22 25), and increase it by 4, it produces a feasible set $$A=\{4, 6, 11, 17, 25, 26, 29\} \implies f( 118 ) \geqslant 2203567.$$ (Maybe I was just lucky here, I didn't play a lot with Golomb rulers.)

It is not hard to see that $f$ grows stronger than any polynomial. In fact, for a given $k$, we can start with a feasible set $A=\{a_1,\dots,a_k\}$ (and such a set exists, e.g. $A=\{2,4,8,\dots,2^k\}$, which is very wasteful but sufficient here) and put $s:=a_1+\cdots+a_k$. Then, to be even more generous, each set $A+ks, A+ks+1,...$ is feasible as well, and the heights of $q_{A+ks+n},n\in\mathbb N,$ are $O(n^k)$. A very loose exponential lower bound is given by $f(2^n) \geqslant 2^{\binom{n-1}2}$. Empirically, something like $f(n) \geqslant \exp(n/7)$ seems possible. So the obvious question is:

What would be (maybe at least asymptotically) a not-to-loose lower bound of $f(n)$?

Source Link
Wolfgang
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

Flat polynomials with factors of big height

Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call this maximum $f(n)$. Then we have e.g. a lower bound $f(13)\geqslant 16$ by the choice of $$\begin{align} p(x)&={(x+1)(x^2-1)(x^4-1)(x^6-1)}\\ &=x^{13} + x^{12} - x^{11} - x^{10} - x^9 - x^8 + x^5 + x^4 + x^3 + x^2 - x - 1\\ &={(x-1)^3}(x^{10} + 4x^9 + 8x^8 + 12x^7 + 15x^6 + 16x^5 + 15x^4 + 12x^3 + 8x^2 + 4x + 1) \end{align}$$ A promising construction is to start with a certain set $A=\{a_1,\dots,a_k\}$ and consider the polynomial $$p_A:=p_A(x)=\prod_{j=1}^k(x^{a_j}-1) \text{ and its divisor }q_A(x):=\frac{p_A(x)}{(x-1)^k}.$$

If $A$ is feasible (meaning that all coefficients of $p_A$ are in $\{-1,0,1\}$), it may be a good candidate, as the terms in the middle of the (symmetric and unimodal) polynomials $q_A(x)$ can be quite big. I have no idea whether these polynomials are the best possible ones, but you may judge by some examples that they can have factors with quite impressive heights:

$$\begin{align} A=\{2,5,7,8,9\} &\implies f(31)\geqslant 450 \\ A=\{2,6,8,10,13,14\} &\implies f(53)\geqslant 9736\\ A=\{4,7,12, 17,18,19\} &\implies f(77)\geqslant 75552\\ A=\{2, 6, 8, 17, 22, 25, 28\} &\implies f( 108 ) \geqslant 697675. \end{align}$$

As the number of elements of $A$ grows, it is increasingly difficult to come up with feasible sets which have relatively small elements. A necessary and sufficient condition for feasibility is that $A$ is "even-sum-free" (e.s.f.), for lack of a better term, meaning that any two subsets of even order have pairwise different sums, and any two subsets of odd order have pairwise different sums. This condition ensures that each power of $x$ occurs at most once in $p_A$, so it is sufficient. To see that it is also necessary, assume $A$ has a pair of (wlog disjoint) subsets of same parity and same sums. Consider one where this sum is maximal. The corresponding coefficient $\pm2$ cannot be compensated by other subsets without producing a coefficient $\pm2$ in a term of higher order, so this set is not feasible.

Note that those sets have similar features as Sidon sets, a.k.a. Golomb rulers. By the way, if we take the last of the optimal Golomb rulers of order 7, viz. (0 2 7 13 21 22 25), and increase it by 4, it produces a feasible set $$A=\{4, 6, 11, 17, 25, 26, 29\} \implies f( 118 ) \geqslant 2203567.$$ (Maybe I was just lucky here, I didn't play a lot with Golomb rulers.)

It is not hard to see that $f$ grows stronger than any polynomial. In fact, for a given $k$, we can start with a feasible set $A=\{a_1,\dots,a_k\}$ (and such a set exists, e.g. $A=\{2,4,8,\dots,2^k\}$, which is very wasteful but sufficient here) and put $s:=a_1+\cdots+a_k$. Then, to be even more generous, each set $A+ks, A+ks+1,...$ is feasible as well, and the heights of $q_{A+ks+n},n\in\mathbb N,$ are $O(n^k)$.

So the obvious question is:

What would be (maybe at least asymptotically) a good lower bound of $f(n)$?

And a side question:

Are there classes of polynomials which do significantly better than the $p_A$'s when it comes to heights of factors?

A word about my motivation: Believe it or not $-$ I got the idea of this question when I was mulling about the coefficients of the cyclotomic polynomial $\Phi_{105}$. Now you will certainly agree that $x^{105}-1$ is a rather poor candidate for that matter...