Erdős Problem #177

Erdős Problem 177: one colouring controlling every common difference

1. Statement and scope

Seek one function $f:\mathbb N\to\{-1,1\}$ for which sums on every finite arithmetic progression of difference $d$ are bounded by a function $h(d)$, and determine the best growth of such a bound. We construct a single function with the explicit estimate \[ \sup_{a,s\ge1}\left|\sum_{j=0}^{s-1}f(a+jd)\right| \le\frac{L_d}{d}\le4(d-1)!\qquad(d\ge1).\tag{1} \] This reconstructs the classical factorial-scale existence phenomenon. It does not match the much stronger polynomial bounds recorded on the problem page, and the optimal-growth question remains unresolved.

2. Balanced nested words

A word is a finite list of signs, indexed from one. Start with $W_0=(1)$ and $L_0=1$. Given $W_{m-1}$ of length $L_{m-1}$, set \[ q_m=\frac{m}{\gcd(m,L_{m-1})},\qquad X_m=\underbrace{W_{m-1}\cdots W_{m-1}}_{q_m\text{ copies}}, \qquad W_m=X_m(-X_m). \] Here $-X_m$ changes every sign. Its length is \[ L_m=2\operatorname{lcm}(m,L_{m-1}).\tag{2} \] We claim that $L_m$ is divisible by each $1\le d\le m$ and that, in $W_m$, the signs at positions in each fixed residue class modulo $d$ sum to zero.

Inductively, for $d<m$, every copy of $W_{m-1}$ or its negative has zero sum in each such residue, and its length is divisible by $d$. Concatenation preserves this. For $d=m$, the length of $X_m$ is divisible by $m$. Corresponding positions of $X_m$ and $-X_m$ therefore belong to the same residue class and cancel. This proves the claim, including the base case $W_1=(1,-1)$.

Every $W_m$ begins with $W_{m-1}$, and the lengths tend to infinity. They consequently specify one infinite sign sequence $f$. For each fixed $d$, all later words, and hence this entire sequence, are concatenations of copies of $W_d$ and $-W_d$ in blocks of length $L_d$.

3. Uniform control for arbitrary starts and lengths

Fix $d$ and one of these aligned blocks. A progression of difference $d$ uses positions of one residue modulo $d$. There are exactly $L_d/d$ such positions in a full block, with equal numbers of positive and negative signs by the construction. Thus a full block contributes zero, and the absolute sum on any segment of this residue word is at most $L_d/(2d)$: it cannot contain more positive or negative signs than the entire balanced word does.

A finite progression intersects a string of full blocks and at most two partial end blocks. Its absolute sum is therefore at most $L_d/d$. A progression inside just one block obeys the stronger half-sized bound, so it causes no exception. This proves the first inequality in $1$, for all starting points and all lengths, using the same $f$ simultaneously for every $d$.

4. An explicit factorial estimate

The recurrence $2$ gives the exact formula \[ L_d=2^d\operatorname{lcm}\{j:1\le j\le d,\ j\text{ odd}\}.\tag{3} \] To check this, the odd part evolves by taking the least common multiple with the odd part of $d$. The exponent of two increases by one at every stage: for $d\ge2$ we have $v_2(d)\le d-1$, so the previous factor $2^{d-1}$ already contains the two-part of $d$. The case $d=1$ starts with $L_1=2$.

Bounding the least common multiple by the product of the odd integers gives \[ \frac{L_d}{d} \le\frac{2^{\lceil d/2\rceil}}{\lfloor d/2\rfloor!}(d-1)! \le4(d-1)!. \] For the last inequality, if $r\ge1$ then $r!\ge2^{r-1}$; use $d=2r$ and $d=2r+1$ separately, and check $d=1$ directly. This establishes $1$ with a uniform numerical constant.

5. Necessary qualifications and the missing improvement

No periodic sign sequence can work for every $d$: for a period $p$, its values on $a,a+p,a+2p,\ldots$ are constant, giving unbounded sums. Our construction uses nested finite words rather than a fixed period. Similarly, assigning a different alternating sequence to each $d$ does not solve the simultaneous requirement.

Van der Waerden's theorem, used here only as a standard external input, implies that the discrepancy cannot be bounded by one constant for all $d$: a monochromatic progression of length exceeding that constant contradicts it. More precisely, the nondecreasing envelope \[ H(D)=\max_{1\le d\le D}\sup_{a,s\ge1}\left|\sum_{j=0}^{s-1}f(a+jd)\right| \] must tend to infinity for any function whose individual suprema are finite. This argument by itself does not give a rate, or justify replacing envelope growth by a pointwise lower estimate at every difference.

The current literature records a bound $d^{8+\varepsilon}$ due to Beck, stronger than $1$; that theorem is not reproduced here. The construction above supplies a complete simultaneous bound and corrects the earlier draft's dependence of the colouring on $d$. Determining the optimal smaller growth remains the gap.

Source: https://www.erdosproblems.com/177. The factorial-scale result is classical (Cantor, Erdős, Schreiber and Straus); no novelty is claimed for this reconstruction.

Completion rate estimate: 40%.

PROBLEM

Find the smallest $h(d)$ such that the following holds. There exists a function $f:\mathbb{N}\to\{-1,1\}$ such that, for every $d\geq 1$, \[\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),\] where $P_d$ ranges over all finite arithmetic progressions with common difference $d$.

OUTPUT

1) FORMAL RESTATEMENT

We seek a function $h:\mathbb N\to\mathbb N$ of minimal growth such that there exists a single function $f:\mathbb N\to\{-1,1\}$ with the property:

For every $d\ge 1$, \[ \Delta_f(d):=\sup\left\{\left|\sum_{n\in P} f(n)\right| : P=\{a,a+d,\dots,a+(m-1)d\}\text{ for some }a,m\in\mathbb N\right\}\le h(d). \] (Here $m$ ranges over all positive integers, so $P$ ranges over all finite arithmetic progressions of common difference $d$.)

The problem asks for the smallest possible such $h(d)$ (up to order of magnitude).

---

2) QUICK LITERATURE/CONTEXT CHECK

I will not use or claim any external results beyond what is explicitly written in the problem text.

The problem text reports:

* There exist constructions with $h(d)\ll d!$ (Cantor–Erdős–Schreiber–Straus). * Van der Waerden implies $h(d)\to\infty$. * Beck obtained $h(d)\le d^{8+\varepsilon}$. * Roth gives $h(d)\gg d^{1/2}$.

I do not re-prove these bounds.

---

3) ATTACK PLAN

1. Prove explicit bounds in simplified settings (e.g. controlling a single difference $d$). 2. Prove that $h$ cannot be bounded by an absolute constant if it works for all $d$ (using van der Waerden as allowed by the problem text).

---

4) WORK

Lemma 4.1 (perfect control for a fixed difference $d$ with a tailored function)

Fix $d\ge 1$ and define \[ f_d(n):=(-1)^{\left\lfloor\frac{n-1}{d}\right\rfloor}. \] Then for every finite arithmetic progression $P$ with common difference $d$, \[ \left|\sum_{n\in P} f_d(n)\right|\le 1. \]

Proof. Let $P=\{a,a+d,a+2d,\dots,a+(m-1)d\}$. For each $j\ge 0$, \[ \left\lfloor\frac{(a+jd)-1}{d}\right\rfloor =\left\lfloor\frac{a-1}{d}+j\right\rfloor =\left\lfloor\frac{a-1}{d}\right\rfloor + j. \] Therefore \[ f_d(a+jd)=(-1)^{\lfloor(a-1)/d\rfloor+j}=(-1)^{\lfloor(a-1)/d\rfloor}\cdot (-1)^j. \] So along the progression $P$ the values alternate in sign. Hence \[ \sum_{n\in P} f_d(n)=(-1)^{\lfloor(a-1)/d\rfloor}\sum_{j=0}^{m-1} (-1)^j. \] The alternating sum $\sum_{j=0}^{m-1}(-1)^j$ equals $0$ if $m$ is even and equals $1$ if $m$ is odd. Thus the total sum is in $\{0,\pm 1\}$ and has absolute value at most $1$. $\square$

Remark. This shows that if one were allowed to choose $f$ depending on $d$, then the optimal bound for that single $d$ would be $h(d)=1$. The actual problem is the simultaneous requirement for all $d$ with one fixed $f$.

---

Lemma 4.2 (no uniform constant bound across all differences)

There is no function $f:\mathbb N\to\{-1,1\}$ such that $\Delta_f(d)\le H$ for all $d$ with a fixed constant $H$. Consequently any admissible $h(d)$ must be unbounded.

Proof. Assume for contradiction that there exist $f$ and a constant $H$ such that for every $d$, every finite $d$-progression has sum of absolute value at most $H$. Interpret $f$ as a 2-coloring of $\mathbb N$ (color $+1$ vs $-1$).

By van der Waerden’s theorem (as referenced in the problem text), for each integer $m>H$ there exists a monochromatic arithmetic progression $P$ of length $m$ in this 2-coloring. On that progression, $f$ is constant, so \[ \left|\sum_{n\in P} f(n)\right|=m>H, \] contradicting the assumed uniform bound.

Therefore no such uniform constant exists, so any admissible function $h(d)$ must satisfy $\sup_d h(d)=\infty$. $\square$

---

5) VERIFICATION

* Lemma 4.1: the key identity $\lfloor((a+jd)-1)/d\rfloor=\lfloor(a-1)/d\rfloor+j$ is correct because $j$ is an integer. * Lemma 4.2: the only external input is van der Waerden’s theorem, explicitly mentioned in the problem text.

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

I proved:

* For each fixed $d$ there exists a tailored $f_d$ with discrepancy at most $1$ on all $d$-progressions (Lemma 4.1). * No single $f$ can have a uniform constant discrepancy bound across all differences $d$ (Lemma 4.2).

(ii) Exact first gap.

Construct a single function $f$ that simultaneously controls all $d$ with an explicit small-growth function $h(d)$, or prove lower bounds showing such control must be large (e.g. polynomial).

(iii) Top 3 next moves (concrete targets).

1. Try to combine periodic/block constructions at many scales (e.g. Chinese remainder style) to produce one $f$ with $h(d)$ poly$(d)$. 2. Prove a clean lower bound mechanism: show that any $f$ forces some difference $d$ to have discrepancy at least $\Omega(d^\alpha)$ for some $\alpha>0$. 3. For small $d$, compute (by search) the minimal achievable $\Delta_f(d)$ under constraints for multiple differences simultaneously, to guess the right growth.

(iv) What a minimal counterexample would likely look like.

A counterexample to “polynomial $h(d)$ is possible” would be a proof that any $f$ necessarily has very large discrepancy on progressions of some moderately large difference $d$ (perhaps using a density increment argument). Such a proof would likely show that controlling many differences forces a structured bias that creates long monochromatic APs.