we-solve (beta)

Math-734-A2 · revision r1 · on Math-734

gpt pro 5.2 attempt on Math-734

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #256
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Tiny cases / sanity checks.
  7. Known upper bound (input).
  8. Elementary comparison lemma.
  9. Disproof of $(\star)$.
  10. 5) VERIFICATION
  11. 6) FINAL
  12. 7) COMPLETION ESTIMATE (MANDATORY)

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.
Theorem (Belov--Konyagin, consequence for $f(n)$ [BeKo96]): There exists an absolute constant $C>0$ such that for all $n\ge 2$, \[ \log f(n)\le C\,(\log n)^4. \] Equivalently, $f(n)\le \exp\left(C(\log n)^4\right)$ for all $n\ge 2$.
Elementary comparison lemma.
Lemma: For every $c>0$, one has $(\log n)^4 = o(n^c)$ as $n\to\infty$. Equivalently, \[\lim_{n\to\infty}\frac{(\log n)^4}{n^c}=0.\]
Proof: Fix $c>0$ and set $\varepsilon:=c/8$. Consider the function $g(x)=x^{\varepsilon}/\log x$ for $x>e$. Then \[ \log g(x)=\varepsilon\log x-\log\log x\xrightarrow[x\to\infty]{}+\infty, \] so $g(x)\to\infty$. In particular, there exists $x_0$ such that for all $x\ge x_0$, \[\log x \le x^{\varepsilon}. \] For $n\ge x_0$ this gives $(\log n)^4 \le n^{4\varepsilon}=n^{c/2}$, hence \[ 0\le \frac{(\log n)^4}{n^c}\le \frac{n^{c/2}}{n^c}=n^{-c/2}\xrightarrow[n\to\infty]{}0. \] ∎
Disproof of $(\star)$.
Proposition: Statement $(\star)$ is false; i.e. there is no constant $c>0$ such that $\log f(n)\gg n^c$.
Proof: Assume for contradiction that $(\star)$ holds. Then there exist $c>0$, $K>0$ and $n_0$ such that $\log f(n)\ge K n^c$ for all $n\ge n_0$.

On the other hand, by the Belov--Konyagin bound there is $C>0$ such that for all $n\ge 2$, $\log f(n)\le C(\log n)^4$. By Lemma Lemma, $(\log n)^4=o(n^c)$, so we may choose $n_1$ such that for all $n\ge n_1$, \[C(\log n)^4 < K n^c. \] Taking $n\ge \max\{n_0,n_1,2\}$ gives \[\log f(n)\le C(\log n)^4 < K n^c \le \log f(n), \] a contradiction. ∎

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%.