Reused writeup on Math-5713 (gpt pro 5.2)

Erdős Problem 524 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/524

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/524.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/524.tex.

FORMAL RESTATEMENT. For $t\in(0,1)$, choose a binary expansion \[t=\sum_{k=1}^\infty \epsilon_k(t)2^{-k},\qquad \epsilon_k(t)\in\{0,1\}. \] (For dyadic rationals there are two expansions; these form a countable set of Lebesgue measure $0$, so they can be ignored in "almost all $t$" statements.) Define signs $a_k(t)=(-1)^{\epsilon_k(t)}\in\{-1,1\}$ and for $n\ge 1$ define \[P_n(t;x)=\sum_{k=1}^n a_k(t) x^k,\qquad x\in[-1,1], \] and \[M_n(t)=\max_{x\in[-1,1]} |P_n(t;x)|. \] Question: Determine the correct order of magnitude of $M_n(t)$ for Lebesgue-a.e. $t$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement attributes the question to Salem--Zygmund, and reports (i) a result of Chung that for almost all $t$ there are infinitely many $n$ with $M_n(t)\ll (n/\log\log n)^{1/2}$, and (ii) an (unpublished) result of Erdős that for almost all $t$ and every $\varepsilon>0$, $\lim_{n\to\infty} M_n(t)/n^{1/2-\varepsilon}=\infty$.

ATTACK PLAN.

• Proof track idea 1: Model $a_k(t)$ as i.i.d. Rademacher signs (valid for a.e. $t$) and treat $P_n(t;\cdot)$ as a random process on $[-1,1]$; then control $\sup$ via discretization + concentration or chaining.
• Proof track idea 2: Analyze the contribution near $x=\pm 1$ separately (where variance is $\asymp n$) and compare to a Gaussian process with similar covariance.
• Disproof track: Construct a set of $t$ of positive measure where the digits have atypical long correlations forcing much larger (or much smaller) $M_n(t)$ than any proposed "typical" order.

WORK.

Fast reality check (Monte Carlo, grid-max approximation). We sampled i.i.d. random signs $a_1,\dots,a_n$ and approximated $\max_{x\in[-1,1]}|\sum_{k\le n} a_k x^k|$ on a uniform grid of $8001$ points. For 30 samples each $n$:

{'n': 10, 'samples': 30, 'avg_M': 3.9466599700994154, 'min_M': 2.0, 'max_M': 8.0}
{'n': 20, 'samples': 30, 'avg_M': 5.552696460366131, 'min_M': 1.2789913066823837, 'max_M': 12.0}
{'n': 50, 'samples': 30, 'avg_M': 7.169544432138646, 'min_M': 2.0, 'max_M': 18.0}
{'n': 100, 'samples': 30, 'avg_M': 13.390316749438387, 'min_M': 2.394691054102984, 'max_M': 26.0}

These are only numerical sanity checks (grid approximation; finite samples).

Lemma 524.1 (binary digits are i.i.d. for Lebesgue-a.e. $t$). Let $t$ be uniformly distributed on $(0,1)$ (Lebesgue measure). Then for each fixed $m\ge 1$, the vector $(\epsilon_1(t),\dots,\epsilon_m(t))$ is uniform on $\{0,1\}^m$. In particular, the coordinate digits $(\epsilon_k(t))_{k\ge 1}$ are independent Bernoulli$(1/2)$ random variables, and $(a_k(t))_{k\ge 1}$ are independent uniform signs.

Proof. Fix $m\ge 1$ and fix a pattern $(b_1,\dots,b_m)\in\{0,1\}^m$. The set \[A_{b_1,\dots,b_m}=\{t\in(0,1): \epsilon_1(t)=b_1,\dots,\epsilon_m(t)=b_m\} \] consists of exactly the dyadic interval \[\Big[\sum_{k=1}^m b_k 2^{-k},\ \sum_{k=1}^m b_k 2^{-k}+2^{-m}\Big) \] except possibly for its right endpoint (a dyadic rational). Therefore its Lebesgue measure is exactly $2^{-m}$. Since there are $2^m$ such patterns and the intervals form a partition of $(0,1)$ up to endpoints, it follows that $(\epsilon_1,\dots,\epsilon_m)$ is uniform on $\{0,1\}^m$. Uniformity for all $m$ implies the digits are i.i.d. Bernoulli$(1/2)$, and then $a_k=(-1)^{\epsilon_k}$ are i.i.d. uniform signs. $\square$

Lemma 524.2 (a crude almost sure upper bound: $M_n(t)=O(\sqrt{n\log n})$). There exists an absolute constant $C>0$ such that for Lebesgue-a.e. $t$, \[M_n(t) \le C\sqrt{n\log n}\qquad\text{for all sufficiently large }n. \]

Proof. By Lemma 524.1 we may treat $(a_k(t))_{k\ge 1}$ as i.i.d. uniform signs on a probability space. Fix $n\ge 2$ and define the random polynomial \[P_n(x)=\sum_{k=1}^n a_k x^k,\qquad x\in[-1,1]. \]

Step 1: concentration at a fixed point. Fix $x\in[-1,1]$. The summands $X_k=a_k x^k$ are independent, mean $0$, and satisfy $|X_k|\le |x|^k\le 1$. Hoeffding's inequality therefore gives, for any $t>0$, \[\mathbb P\big(|P_n(x)|\ge t\big) \le 2\exp\Big(-\frac{t^2}{2\sum_{k=1}^n |x|^{2k}}\Big). \] Since $\sum_{k=1}^n |x|^{2k}\le n$, we obtain the uniform bound \[\mathbb P\big(|P_n(x)|\ge t\big) \le 2\exp\Big(-\frac{t^2}{2n}\Big)\qquad (x\in[-1,1]). \tag{*} \]

Step 2: discretize $[-1,1]$. For each $n$, let $\mathcal G_n$ be a uniform grid in $[-1,1]$ with spacing $\delta_n=1/n^2$. Then $|\mathcal G_n|\le 2n^2+1\le 3n^2$ for $n\ge 2$.

We also bound the derivative deterministically: \[|P_n'(x)| = \Big|\sum_{k=1}^n k a_k x^{k-1}\Big| \le \sum_{k=1}^n k |x|^{k-1} \le \sum_{k=1}^n k = \frac{n(n+1)}{2} \le n^2\qquad (x\in[-1,1]).\] Thus $P_n$ is $n^2$-Lipschitz on $[-1,1]$. Therefore for every $x\in[-1,1]$ there exists $y\in\mathcal G_n$ with $|x-y|\le\delta_n$ and \[|P_n(x)|\le |P_n(y)| + n^2|x-y| \le |P_n(y)|+1. \] Taking maxima, \[M_n\le 1 + \max_{y\in\mathcal G_n} |P_n(y)|.\tag{**} \]

Step 3: union bound on the grid. Set $t_n=\sqrt{10 n\log n}$. By $*$ and the union bound, \[\mathbb P\Big(\max_{y\in\mathcal G_n}|P_n(y)|\ge t_n\Big) \le |\mathcal G_n|\cdot 2\exp\Big(-\frac{t_n^2}{2n}\Big) \le 3n^2\cdot 2\exp\big(-5\log n\big) =6 n^{-3}. \] This series is summable: $\sum_{n\ge 2} 6n^{-3}<\infty$. By the Borel--Cantelli lemma, almost surely there exists $n_0$ such that for all $n\ge n_0$, \[\max_{y\in\mathcal G_n}|P_n(y)|<t_n. \] Combining with $**$ yields for all $n\ge n_0$, \[M_n < 1 + \sqrt{10 n\log n} \le C\sqrt{n\log n} \] with e.g. $C=\sqrt{10}+1$. Translating back from randomness of $a_k$ to Lebesgue-a.e. $t$ via Lemma 524.1 completes the proof. $\square$

VERIFICATION.

• Lemma 524.1: The only subtlety is the non-uniqueness of binary expansions at dyadic rationals; we explicitly noted this is measure $0$.
• Lemma 524.2: We used Hoeffding with bounds $|X_k|\le 1$ and variance proxy $\sum |x|^{2k}\le n$. The derivative bound is deterministic and holds for all sign choices.
• The Borel--Cantelli application requires summability, which we checked: $6n^{-3}$ is summable.
• The bound is crude; it does not match the sharper $\sqrt{n/\log\log n}$-type behavior mentioned in the problem statement.

FINAL. UNRESOLVED

(i) Strongest proved partial result: For Lebesgue-a.e. $t$, $M_n(t)=O(\sqrt{n\log n})$ (Lemma 524.2).

(ii) First gap (crisp): Determine the true almost-sure order of $M_n(t)$, i.e. sharpen the upper bound and prove a matching lower bound on the correct scale (the problem statement suggests subtle iterated-log effects).

(iii) Top 3 next moves (concrete):

1. Replace the crude grid+Hoeffding argument by a chaining/entropy bound using the covariance structure of $P_n(x)$ to reduce the extra $\sqrt{\log n}$ factor.
2. Prove a lower bound by constructing, for typical sign sequences, a point $x$ close to $1$ (or $-1$) where partial sums add constructively, e.g. show that for a.e. $t$ there exist infinitely many $n$ with $M_n(t)\ge c\sqrt{n\log\log n}$.
3. Computation: estimate $M_n/\sqrt{n}$ and $M_n\sqrt{\log\log n/n}$ for larger $n$ in simulations with finer maximization (e.g. optimizing over $x$ by derivative root-finding) to guess the right normalization.

(iv) Minimal counterexample structure: If a proposed order (e.g. $\asymp \sqrt{n}$) is false, a counterexample for "almost all $t$" would have to show that typical digit sequences force larger growth (e.g. $\sqrt{n\log\log n}$) or smaller growth infinitely often. Such behavior would likely be driven by rare long runs/blocks in the binary digits that create near-geometric alignment of signs for $x$ extremely close to $\pm 1$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.