Erdős Problem #176

Erdős Problem 176: exact low-threshold values and an exponential obstruction

1. Statement and scope

Let $N(k,\ell)$ be the least interval length forcing a $k$-term arithmetic progression whose sum in every $\{-1,1\}$-colouring has absolute value at least $\ell$. The interesting range is $0<\ell\le k$: for $\ell>k$ the value is infinite. In particular a proposed bound for $\ell=ck$ must restrict to $0<c\le1$.

We reconstruct the exact formula for $N(k,1)$ attributed to Spencer, including a matching colouring, and a local-lemma exponential lower bound for linear thresholds. The general exponential upper-bound questions remain unresolved. For finiteness alone, van der Waerden's theorem is an explicit standard input: $N(k,\ell)\le W(k)$ when $\ell\le k$.

2. Exact formula at the smallest positive threshold

Write $k=cm$, where $c=2^t$ and $m$ is odd. We prove \[ N(k,1)=c(k-1)+1.\tag{1} \] For the upper bound let $N=c(k-1)+1$ and suppose every $k$-term progression has sum zero. Comparing consecutive length-$k$ intervals shows \[ f(i+k)=f(i)\qquad(1\le i\le N-k). \] Thus $f$ is $k$-periodic wherever the two arguments lie in $[1,N]$. The progression $1,1+c,\ldots,1+(k-1)c$ is contained in this interval. Modulo $k$, it visits the $m$ residue classes $1,1+c,\ldots,1+(m-1)c$ exactly $c$ times each. Its sum is therefore $c$ times a sum of $m$ signs, which is nonzero because $m$ is odd. This contradiction proves the upper bound. When $c=1$, the same argument is simply the parity of the sum on $[k]$.

For the lower bound consider $[1,c(k-1)]$. If $c=1$ there is no $k$-term progression. Otherwise colour $n$ by $(-1)$ raised to the sum of the lowest $t$ binary digits of $n-1$. This colouring is $c$-periodic. Any $k$-term progression in the interval has positive difference $d<c$. Put $g=\gcd(d,c)$; then $g<c$, and addition of $d$ modulo $c$ traverses one whole residue class modulo $g$, with period $c/g$. Since $g$ is a power of two, the low binary digits fixed by that residue class stay fixed, while at least one higher digit ranges freely. Pairing residues by flipping that digit proves that the signs on the cycle sum to zero. Since $k$ is a multiple of $c/g$, the progression consists of complete cycles and has sum zero. This proves $1$.

For even $k$, every progression sum is even, so the thresholds one and two coincide: \[ N(k,2)=N(k,1)\le k(k-1)+1\qquad(k\text{ even}).\tag{2} \] For odd $k$, $N(k,1)=k$ but threshold two means an absolute sum at least three. It is not covered by $2$. In particular there is no monotonicity in $k$ of the kind asserted in the earlier draft: $N(4,1)=13$ but $N(5,1)=5$.

3. A finite local lemma, with the needed justification

We use the following elementary probability lemma. If events $E_i$ have a dependency graph, and numbers $0<x_i<1$ satisfy \[ \mathbb P(E_i)\le x_i\prod_{j\sim i}(1-x_j),\tag{3} \] then there is positive probability that none occurs. Here nonadjacency means independence from the entire collection of nonneighbour events, as holds for events depending on disjoint sets of independent signs.

For completeness, induction on $|S|$ proves $\mathbb P(E_i\mid\bigcap_{j\in S}E_j^c)\le x_i$. Split $S$ into neighbours of $i$ and nonneighbours. Conditioning on the latter does not change the probability of $E_i$. Introducing the neighbour conditions divides by a probability at least the product of their $1-x_j$, using the induction hypothesis successively. Inequality $3$ bounds the resulting quotient by $x_i$. If there are no neighbours in $S$, independence gives the result directly. The same induction guarantees all conditioning probabilities are positive. Multiplying the successive probabilities of avoiding the events now gives a positive product.

In particular, if each event has at most $B-1$ neighbours, with integer $B\ge2$, and probability at most $1/(4B)$, choose $x_i=1/B$. The inequality $(1-1/B)^{B-1}\ge1/4$ verifies $3$.

4. Applying it to progression discrepancies

Assume $k\ge2$ in this section and choose independent uniform signs on $[1,N]$. For a fixed $k$-term progression, the probability that its absolute sum is at least $\ell$, for $0<\ell\le k$, is exactly \[ q=2^{1-k}\sum_{i=\lceil(k+\ell)/2\rceil}^k\binom ki.\tag{4} \] The two tails are disjoint and symmetric, including the correct parity cutoff. A point lies in at most $kN/(k-1)\le2N$ $k$-term progressions: choose its position among the $k$ terms and a positive difference at most $(N-1)/(k-1)$. A progression therefore meets at most $2kN-1$ others. With $B=2kN$, the lemma implies an avoiding colouring whenever $qB\le1/4$. Consequently, if the integer on the right is at least $k$, \[ N(k,\ell)>\left\lfloor\frac1{8kq}\right\rfloor.\tag{5} \] For $\ell=ck$ with fixed $0<c<1$, the moment-generating function $(\cosh\lambda)^k$ and Markov's inequality give \[ q\le2e^{-kI(c)},\qquad I(c)=\frac{1+c}{2}\log(1+c)+\frac{1-c}{2}\log(1-c). \] Indeed minimise $e^{-\lambda ck}(\cosh\lambda)^k$ at $\lambda=\tfrac12\log((1+c)/(1-c))$ and use symmetry for the other tail. Thus $5$ gives an exponential lower bound with rate $I(c)$, up to a factor $16k$. At $c=1$, the exact probability is $2^{1-k}$ and the same argument gives $N(k,k)>\lfloor2^k/(16k)\rfloor$. The limiting exponential base as $c\uparrow1$ is two.

5. Assessment and attribution

The exact low-threshold values, their matching binary colouring and the probabilistic lower bound are completely justified. They do not yield the requested exponential upper bounds for odd $k$ at threshold two, for $\sqrt k$, or for a fixed positive fraction of $k$. The exact formula is Spencer's result; the local-lemma improvement is recorded in Hunter's comment on the source page. These are reconstructions, not novelty claims.

Source: https://www.erdosproblems.com/176.

Completion rate estimate: 40%.

PROBLEM

Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that \[ \left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell.\] Find good upper bounds for $N(k,\ell)$. Is it true that for any $c>0$ there exists some $C>1$ such that $N(k,ck)\leq C^k$?

OUTPUT

1) FORMAL RESTATEMENT

Fix integers $k\ge 3$ and $\ell\ge 1$.

For $N\ge 1$ and a function $f:[N]:=\{1,2,\dots,N\}\to\{-1,1\}$, and a $k$-term arithmetic progression \[ P(a,d):=\{a,a+d,\dots,a+(k-1)d\}\subseteq [N], \] define its signed sum \[ S_f(P):=\sum_{n\in P} f(n). \]

Define $N(k,\ell)$ to be the smallest $N$ such that for every $f:[N]\to\{-1,1\}$ there exists a $k$-term AP $P\subseteq [N]$ with \[ |S_f(P)|\ge \ell. \] If no such $N$ exists, set $N(k,\ell)=\infty$ (but for $\ell\le k$ it is finite by van der Waerden-type reasoning).

The question asks for good upper bounds on $N(k,\ell)$, and specifically whether for each $c>0$ there exists $C>1$ with $N(k,ck)\le C^k$.

---

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 notes:

* When $\ell=k$, $N(k,k)$ equals the van der Waerden number $W(k)$. * Spencer computed $N(k,1)$ exactly for $k=2^t m$ with $m$ odd. * Erdős proved an exponential lower bound for $N(k,ck)$.

I do not re-prove Spencer’s or Erdős’s results.

---

3) ATTACK PLAN

1. Prove elementary base-case facts (e.g. $N(k,1)=k$ for odd $k$). 2. Relate $N(k,\ell)$ to van der Waerden numbers to get a trivial upper bound $N(k,\ell)\le W(k)$ for $\ell\le k$. 3. Compute small values of $N(k,\ell)$ for small $(k,\ell)$ by brute force enumeration of all signings.

---

4) WORK

Phase 1: FAST REALITY CHECK (small exact values)

I computed $N(k,\ell)$ for a few small cases by enumerating all $2^N$ functions $f:[N]\to\{-1,1\}$. The results:

* $N(3,1)=3$. * $N(3,2)=9$. * $N(4,1)=13$. * $N(4,2)=13$ (for even $k$, the sum over a $k$-AP is even, so the conditions $|S|\ge 1$ and $|S|\ge 2$ coincide).

---

Lemma 4.1 (odd $k$ forces $N(k,1)=k$)

If $k$ is odd, then \[ N(k,1)=k. \]

Proof. First, if $N<k$ then there is no $k$-term arithmetic progression in $[N]$, so $N(k,1)\ge k$.

Now take $N=k$. The set $[k]$ itself is a $k$-term arithmetic progression with $a=1$, $d=1$. For any $f:[k]\to\{-1,1\}$, \[ S_f([k])=\sum_{n=1}^k f(n). \] This is a sum of $k$ odd integers ($\pm 1$), hence is an odd integer. Therefore $S_f([k])\ne 0$, so $|S_f([k])|\ge 1$. Thus every $f$ has a $k$-term AP with discrepancy at least 1 already in $[k]$, showing $N(k,1)\le k$. Combining gives equality. $\square$

---

Lemma 4.2 (trivial van der Waerden upper bound)

For every $k\ge 3$ and every $1\le \ell\le k$, \[ N(k,\ell)\le W(k), \] where $W(k)$ is the 2-color van der Waerden number.

Proof. Let $N=W(k)$. Given any $f:[N]\to\{-1,1\}$, view it as a 2-coloring of $[N]$ by colors “$+1$” and “$-1$”. By definition of $W(k)$, there exists a monochromatic $k$-term arithmetic progression $P\subseteq[N]$. On such a $P$, either $f\equiv +1$ or $f\equiv -1$, so \[ S_f(P)=\pm k. \] Thus $|S_f(P)|=k\ge \ell$. This shows that for $N=W(k)$ every $f$ has a $k$-AP with discrepancy at least $\ell$, i.e. $N(k,\ell)\le W(k)$. $\square$

---

Lemma 4.3 (monotonicity)

If $k'\ge k$ and $\ell'\ge \ell$ then \[ N(k',\ell')\ge N(k,\ell). \]

Proof. The condition “there exists a $k'$-AP with $|S_f|\ge \ell'$” is stronger than “there exists a $k$-AP with $|S_f|\ge \ell$” because it asks for longer progressions and a larger discrepancy threshold. Therefore achieving the stronger guarantee for all $f$ cannot require a smaller ambient interval. Formally, if $N$ works for $(k',\ell')$, then in particular it works for $(k,\ell)$ by restricting attention to $k$-APs and using $\ell\le \ell'$. Hence the minimal such $N$ satisfies the stated inequality. $\square$

---

5) VERIFICATION

* Lemma 4.1: the key is that a sum of an odd number of $\pm 1$ values is odd and hence nonzero. * Lemma 4.2: correct use of the definition of $W(k)$. * Computed small values are consistent with Lemma 4.1: $N(3,1)=3$. Also $N(3,2)=9$ matches the interpretation that $\ell=2$ for $k=3$ forces a monochromatic 3-AP.

---

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

Elementary facts:

* For odd $k$, $N(k,1)=k$ (Lemma 4.1). * For all $\ell\le k$, $N(k,\ell)\le W(k)$ (Lemma 4.2). * Monotonicity in parameters (Lemma 4.3).

And exact small values: $N(3,1)=3$, $N(3,2)=9$, $N(4,1)=13$, $N(4,2)=13$.

(ii) Exact first gap.

Prove nontrivial upper bounds (e.g. $N(k,2)\le C^k$) beyond the van der Waerden bound, which is far too large.

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

1. For fixed small $\ell$ (e.g. $\ell=2$), attempt to prove an exponential upper bound via probabilistic/entropy methods on the family of $\pm 1$ colorings. 2. For $\ell=ck$, seek a “density increment” or Fourier-analytic approach: large discrepancy means biased color distribution along an AP. 3. Compute $N(k,2)$ for moderate $k$ by SAT/ILP to guess growth and candidate extremal colorings.

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

A counterexample to $N(k,2)\le C^k$ would be a sequence of signings $f_k$ on $[N_k]$ with $N_k$ super-exponential in $k$ such that every $k$-AP has sum in $\{-0,\pm 2\}$ (i.e. extremely balanced). Such a sequence would likely require highly structured, pseudorandom-like sign patterns.