Erdős Problem #256

Erdős Problems #256--#258: Round 2 continuation

Erdős Problem #256

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. Round 1 already gave a complete disproof of the specific subquestion \[ \exists c>0\text{ such that }\log f(n)\gg n^c. \] So the only legitimate round-2 task here is to adversarially check that disproof, lock in the quantifiers, and record the minimal corrected conclusion.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts without re-proving them.

1. Belov--Konyagin's upper bound: there exists an absolute constant $C>0$ such that \[ \log f(n)\le C(\log n)^4 \] for all sufficiently large $n$.
2. The elementary comparison \[ (\log n)^4=o(n^c)\qquad (n\to\infty) \] for every fixed $c>0$.
3. The Round-1 contradiction argument combining $1$ and $2$.

3) NEW INSIGHT / TOOL (ROUND-2)

There is no new mathematical ingredient needed. The only new point is an adversarial consistency check against the current Erdős Problems summary, which now explicitly records that the specific power-lower-bound question has a negative answer.

4) ATTACK PLAN (ROUND-2)

The only possible gap after Round 1 would have been a quantifier slip: one must rule out every fixed exponent $c>0$, not just a particular one. The plan is therefore to re-run the contradiction with the quantifiers written explicitly.

5) WORK (ROUND-2)

Fix any $c>0$. Suppose, for contradiction, that there exist $K>0$ and $n_0$ such that \[ \log f(n)\ge K n^c\qquad (n\ge n_0). \] Round 1 already established that there is an absolute constant $C>0$ such that \[ \log f(n)\le C(\log n)^4 \] for all sufficiently large $n$. Since $(\log n)^4=o(n^c)$, there exists $n_1$ such that \[ C(\log n)^4<K n^c\qquad (n\ge n_1). \] Hence, for all sufficiently large $n$, \[ \log f(n)\le C(\log n)^4<K n^c\le \log f(n), \] which is impossible. Therefore no fixed $c>0$ can satisfy $\log f(n)\gg n^c$.

Thus the specific subquestion in Problem #256 is fully settled in the negative.

6) ADVERSARIAL VERIFICATION

1. Quantifiers. The argument starts with an arbitrary fixed $c>0$ and shows that this $c$ cannot work. Hence it rules out all $c>0$.
2. Dependence of constants. The Belov--Konyagin constant $C$ is absolute; the contradiction only needs that $C$ is independent of $n$.
3. Logical target. The original question only asked whether a power-type lower bound $\log f(n)\gg n^c$ could hold. The argument disproves exactly that claim, not the entire surrounding estimation problem for $f(n)$.

No gap remains.

7) FINAL

FULL SOLUTION --- COUNTEREXAMPLE / DISPROOF

The specific claim \[ \exists c>0\text{ such that }\log f(n)\gg n^c \] is false. Belov--Konyagin give the upper bound $\log f(n)\ll (\log n)^4$, and $(\log n)^4=o(n^c)$ for every fixed $c>0$. Hence no power lower bound of the form $\log f(n)\gg n^c$ can hold.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 100%

9) REFERENCES

1. A. S. Belov and S. V. Konyagin, An estimate of the free term of a non-negative trigonometric polynomial with integer coefficients, Izv. Math. 60 $1996$, 1123--1182.
2. T. F. Bloom (ed.), Erdős Problem #256, erdosproblems.com/256, accessed 2026-03-07.

Erdős Problem 256: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Let $f(n)$ be the infimum of $\max_{|z|=1}\prod_{i=1}^n|1-z^{a_i}|$ over positive integers $a_1\le\cdots\le a_n$. Estimate its growth; in particular, can $\log f(n)\gg n^c$ hold for some $c>0$? Source: https://www.erdosproblems.com/256.

We prove elementary bounds and reconstruct the analytic transfer from a nonnegative cosine polynomial to a small product. With the explicit Belov--Konyagin input below, this disproves the power lower bound. The broader sharp-growth question remains unresolved here, so this attempt is partial. This replaces the earlier GPT-5.2 draft's full-solution label for only the particular subquestion. No novelty is claimed.

An elementary lower bound

Write $P(z)=\prod_i(1-z^{a_i})=\sum_j c_jz^j$. Its zero at $1$ has multiplicity exactly $n$. It must have at least $n+1$ nonzero coefficients: otherwise, if its $r\le n$ nonzero exponents were $j_1,\ldots,j_r$, the equations \[ \sum_{v=1}^r c_{j_v}j_v(j_v-1)\cdots(j_v-\ell+1)=0 \quad(0\le\ell<r) \] would force all coefficients to vanish. Their matrix is invertible, since the falling-factorial polynomials have degrees $0,\ldots,r-1$ with leading coefficient one and evaluation at distinct $j_v$ is a Vandermonde system. All nonzero $c_j$ are integers. Parseval's identity, obtained by integrating the finite Fourier expansion, gives \[ \max_{|z|=1}|P(z)|^2\ge\frac1{2\pi}\int_0^{2\pi}|P(e^{it})|^2dt =\sum_j c_j^2\ge n+1. \] Thus $f(n)\ge\sqrt{n+1}$. This elementary bound is weaker than known general estimates; no improvement is asserted.

For comparison, $f(1)=2$, and the explicit pair $(1,2)$ gives \[ f(2)\le\max_t8\sin^2(t/2)|\cos(t/2)|=\frac{16}{3\sqrt3}. \] Indeed the maximum of $(1-u)\sqrt u$ on $0\le u\le1$ occurs at $u=1/3$. Combining tuples shows $f(n+m)\le f(n)f(m)$, by taking tuples arbitrarily near their infima. This provides an elementary exponential upper bound better than $2^n$, but not the sharp scale.

A proved transfer from cosine polynomials

Suppose nonnegative integers $b_1,\ldots,b_d$ satisfy $\sum_j b_j=n$ and \[ A+\sum_{j=1}^d b_j\cos(jt)\ge0\quad(t\in\mathbb R). \] For $0<r<1$, the absolutely convergent logarithmic Fourier series yields \[ \sum_j b_j\log|1-r e^{ijt}| =-\sum_{\ell\ge1}\frac{r^\ell}{\ell}\sum_j b_j\cos(j\ell t) \le A\log\frac1{1-r}. \] Also $|1-r e^{iu}|^2=(1-r)^2+r|1-e^{iu}|^2$, so \[ \log\prod_j|1-e^{ijt}|^{b_j} \le-\frac n2\log r+A\log\frac1{1-r}. \tag{1} \] At a zero of the product the inequality holds by continuity. For $n\ge2$, choose $r=1-1/n$. Since $-\log(1-1/n)\le1/(n-1)$, $1$ is at most $1+A\log n$. Thus \[ \log f(n)\le1+A\log n. \tag{2} \] The positive exponents in the required tuple are simply $j$ repeated $b_j$ times; repetitions are permitted by the problem.

Explicit external input and what it settles

Belov and Konyagin prove the existence, for each $n\ge3$, of such a cosine polynomial with $A\ll(\log n)^3$. This is their $K_Z^{\downarrow}(n)$ upper bound in An estimate of the free term of a non-negative trigonometric polynomial with integer coefficients, Izvestiya: Mathematics 60 $1996$, 1123--1182; primary theorem statement: https://www.mathnet.ru/eng/im95. Its long construction is an external dependency, not a proof supplied here.

Substitution into the proved transfer $2$ gives $\log f(n)\ll(\log n)^4$. For any fixed $c>0$, write $u=\log n$; $u^4e^{-cu}\to0$, for example by comparing the exponential series with its fifth term. Consequently no lower bound $\log f(n)\gg n^c$ can hold. This particular negative answer is complete relative to the named cosine-polynomial theorem.

Remaining gap

The elementary lower bound and the polylogarithmic upper bound leave a substantial range for the true growth of $f(n)$. Determining that growth, and reconstructing the deep external cosine-polynomial construction if a fully self-contained upper bound is desired, are not achieved here. Sampling a polynomial on a finite angular grid only gives a lower bound for its maximum; the older draft's sampled values are therefore replaced by the exact two-factor calculation.

Completion rate estimate: 50%.

Erdős Problem #256

1) FORMAL RESTATEMENT

For each integer $n\ge 1$ and each nondecreasing $n$-tuple $(a_1,\dots,a_n)\in\mathbb{N}^n$ (i.e. $a_1\le\cdots\le a_n$), set \[ P_{a_1,\dots,a_n}(z) \;:=\; \prod_{i=1}^n (1-z^{a_i}),\qquad z\in\mathbb{C}. \] For such a tuple define \[ M(a_1,\dots,a_n)\;:=\;\max_{\left\lvert z\right\rvert=1}\,\left\lvert P_{a_1,\dots,a_n}(z)\right\rvert\in[0,\infty). \] (The maximum exists because $z\mapsto\left\lvert P_{a_1,\dots,a_n}(z)\right\rvert$ is continuous on the compact set $\{z\in\mathbb{C}:\left\lvert z\right\rvert=1\}$.) Define \[ f(n)\;:=\;\inf_{a_1\le\cdots\le a_n\in\mathbb{N}} M(a_1,\dots,a_n). \] Equivalently, $f(n)$ is the largest real number such that for every choice of $a_1\le\cdots\le a_n\in\mathbb{N}$ one has \[ \max_{\left\lvert z\right\rvert=1}\left\lvert \prod_{i=1}^n (1-z^{a_i})\right\rvert\;\ge\; f(n). \]

The specific sub-question is the truth of the asymptotic lower bound \[ (\star)\qquad \exists\,c>0\ \exists\,K>0\ \exists\,n_0\ \forall\,n\ge n_0:\ \log f(n)\ge K n^c. \] Here $\log$ denotes the natural logarithm; changing the base rescales $K$ by a constant factor.

2) QUICK LITERATURE/CONTEXT CHECK

(From the standard summary on this problem and the cited papers.)

• Erdős--Szekeres $1959$ showed $f(n)>\sqrt{2n}$ and $\lim_{n\to\infty} f(n)^{1/n}=1$ [ErSz59].
• A long sequence of upper bounds culminates in the result of Belov--Konyagin $1996$: \[\log f(n)\ll (\log n)^4\quad(n\to\infty),\] which in particular gives a negative answer to $(\star)$ [BeKo96].
• Very recently, Tang $2025$ improved the classical general lower bound to \[ f(n)\ge 2\sqrt{n}\quad\text{for all }n\in\mathbb{N},\] the first improvement of the constant in the general lower bound since 1959 [Tang25].

3) ATTACK PLAN

We target $(\star)$. The plan is:

1. Use the known upper bound $\log f(n)\ll(\log n)^4$ (Belov--Konyagin).
2. Prove the elementary comparison $(\log n)^4 = o(n^c)$ for every fixed $c>0$.
3. Conclude that no fixed $c>0$ can satisfy $(\star)$.

4) WORK

Tiny cases / sanity checks.

For $n=1$ and any $a_1\in\mathbb{N}$, \[ M(a_1)=\max_{\left\lvert z\right\rvert=1}\left\lvert 1-z^{a_1}\right\rvert=2, \] because $\left\lvert 1-w\right\rvert\le 2$ for $\left\lvert w\right\rvert=1$ and equality holds at $w=-1$ (so take $z=e^{i\pi/a_1}$). Hence \[ f(1)=2. \] More generally $f(n)\le 2^n$ by taking $a_1=\cdots=a_n=1$, which gives $(1-z)^n$ and $\max_{\left\lvert z\right\rvert=1}\left\lvert 1-z\right\rvert=2$.

As a numerical experiment (not a proof): restricting to $a_i\le 30$ and sampling $\theta$ on a fine grid for $z=e^{i\theta}$ suggests candidates giving \[ M(4,8)\approx 3.0792\quad\text{(so }f(2)\le 3.0792\text{ in this restricted search)}, \] \[ M(2,4,6)\approx 4.3899\quad\text{(so }f(3)\le 4.3899\text{ in this restricted search)}. \] These are only heuristic upper bounds for the true $f(n)$.

Known upper bound (input).

We use the following result.

Elementary comparison lemma.

Disproof of $(\star)$.

5) VERIFICATION

• The logical negation of $(\star)$ is: for every $c>0$ and every $K>0$ there exist arbitrarily large $n$ with $\log f(n)<K n^c$. Proposition Proposition proves this, in fact giving $\log f(n)=O((\log n)^4)$ for all $n$.
• Lemma Lemma is a standard calculus comparison and is proved explicitly.
• The argument uses only: (i) the stated Belov--Konyagin upper bound, and (ii) the elementary fact that polylogarithms are $o(n^c)$.

6) FINAL

LABEL: FULL SOLUTION
SUBLABEL: COUNTEREXAMPLE/DISPROOF
The claim "$\exists c>0$ such that $\log f(n)\gg n^c$" is false. Indeed Belov--Konyagin prove $\log f(n)\ll(\log n)^4$ [BeKo96], and since $(\log n)^4=o(n^c)$ for every $c>0$ (Lemma Lemma), no power lower bound $\log f(n)\gg n^c$ can hold.

7) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 100%.