Komlos 1975 linear problems combinatorial number theory

../

arithmetic_progression_corollary: Specializes the published comparison theorem to give the absolute two-to-the-minus-fifteenth lower comparison for k-term-AP-free subsets.

lemma_1_prime: Compresses a very long increasing integer sequence modulo a smaller integer while keeping all residues distinct.

lemma_2: Retains at least a one-over-alpha fraction while reducing the largest entry to a polylogarithmic multiple of n squared.

lemma_3: Finds a prime modulus with few colliding pairs and retains at least one over two alpha of the entries below n to the three-halves.

lemma_4: Uses two prime moduli to retain one over two alpha squared of a bounded sequence inside an interval of length three n over alpha squared.

lemma_5: Combines the four residue reductions to retain one over four alpha to the sixth of an arbitrary n-element integer set inside the first n integers.

lemma_6: Finds a translate of one subset of the first n integers meeting another in at least their product divided by two n.

lemma_7: For a linear relation not invariant under translation, every set of n integers has a relation-free subset of more than c(d) n elements, with c(d) depending only on the coefficient parameter alpha and on d, the largest excess over 1 of the ratio of positive to negative coefficient sums.

prime_inputs: States the standard prime estimates invoked without proof in the published reduction lemmas.

relation_setup: Fixes the relation, extremal functions, and transfer convention used by the published translation-invariant proof.

remark_3: Shows that sufficiently short residues preserve every solution of the fixed linear relation.

rounding_and_iteration: Supplies integer endpoint calculations and a sufficient log-squared intermediate bound for the translation-invariant comparison proof.

theorem_p114: For every linear relation there is a positive constant c such that, for all large n, every set of n integers has a relation-free subset larger than c times the largest relation-free subset of the first n integers.

translation_invariant_theorem: Proves the explicit one-over-eight-alpha-to-the-sixth comparison between the arbitrary-set and interval extremal functions.

---

János Komlós, Miklós Sulyok, and Endre Szemerédi, Linear problems in combinatorial number theory, Acta Mathematica Academiae Scientiarum Hungaricae 26 (1–2) (1975), 113–121, received November 20, 1973. DOI.

No notice is printed on the article's pages; the publisher's article page shows "© Akadémiai Kiadó 1975", paywalled, and names no open-access or Creative Commons license (https://link.springer.com/article/10.1007/BF01895954, read 2026-10-02), every other right reserved.

Result and proof structure

The main result is the unnumbered Theorem of §1 (printed p. 114): for every linear relation $\varrho$ there is $c(\varrho)>0$ with $g(n)>c(\varrho)f(n)$ for all large $n$, where $f(n)$ is the largest $\varrho$-free subset size inside $\{1,\ldots,n\}$ and $g(n)$ the minimum of the largest $\varrho$-free subset size over all $n$-element sets of integers (setup).

For a translation-invariant relation, with $\alpha$ the maximum row $\ell^1$-norm of the coefficient system, the proof displays, for all sufficiently large $n$,

$$g(n)\geq\frac{1}{8\alpha^6}f(n)$$

(printed p. 116; reconstructed as the translation-invariant comparison). Remark 3 and Lemmas [[additive_combinatorics/komlos_1975_linear_problems_combinatorial_number_theory/lemma_1_prime|$1'$]], 2, 3 and 4 feed Lemma 5; Lemma 6 then completes the translation argument. The prime-number inputs are collected on their own page and the exact rounding on the rounding page. For $k$-term arithmetic progressions $\alpha=4$, so the explicit constant is $2^{-15}$ (progression corollary). Relations not invariant under translation are handled directly by Lemma 7, $g(n)>c(d)n$.

Fidelity and limits

The source's stronger Lemma 1 is explicitly stated without proof and is unused because Lemma $1'$ replaces it. Lemma 7 proves the nontranslation-invariant branch; its page records the statement and the structure of its proof only, and it is not needed for E201. The article's prime-counting estimates are external dependencies; no proof of the prime number theorem is included.

The rewrite makes the source's suppressed integer rounding exact. In Lemma 5 it replaces the printed intermediate $4n^2\log n$ by the directly obtained, still sufficient $O_\alpha(n^2\log^2n)$. The final cardinality constant is unchanged. The printed small endpoint $n\geq2$ in Lemma $1'$ is not needed by the asymptotic theorem, and the displayed source proof does not itself justify all of those small cases; that limitation is recorded on the lemma page.

This is a source reconstruction awaiting independent mathematical review. It does not receive independent proof-review credit here and does not change the open status of E201's ratio-one question.

Bears on. #201: Remark 2 (printed p. 114) names $r_k(n)$ among the translation-invariant relations, and the explicit bound gives $G_k(N)\geq2^{-15}R_k(N)$ for every $k\geq3$ and all large $N$ (the progression corollary), which is the comparison $R_k(N)\ll_kG_k(N)$; it does not decide whether $R_3(N)/G_3(N)\to1$. #530: Remark 2 names $F_k(n)$, the $B_k$-sequence function, among the translation-invariant relations, and the introduction (printed p. 113) records $F_2(n)\sim\sqrt n$; applied to the Sidon condition, the comparison gives every $n$-element set of integers a Sidon subset of size at least $c\sqrt n$ for large $n$. The paper does not display that application, which the problem's claim page writes out; it does not decide whether $\ell(N)\sim N^{1/2}$.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.