Erdős Problem #635

Round-2 continuation for Erdős Problems 633, 634, 635

Correction to the Round-1 draft. The previous draft interchanged the problem numbers. The correct numbering is:

• Problem 633: classify triangles that admit only square-cardinality congruent-triangle dissections.
• Problem 634: determine all $N$ for which some triangle can be dissected into $N$ congruent triangles.
• Problem 635: the divisibility-avoidance problem for subsets of $\{1,\dots,N\}$.

This Round-2 file keeps the valid mathematical progress from Round 1, corrects the numbering error, and then strictly advances each problem.

Erdős Problem 635. Let $t\ge 1$ and $A\subseteq\{1,\dots,N\}$ satisfy: if $a,b\in A$ with $b-a\ge t$, then $(b-a)\nmid b$. How large can $|A|$ be? Is $|A|\le (\tfrac12+o_t(1))N$?

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. The original problem has two parts:

1. determine the exact maximum of $|A|$;
2. prove or disprove the asymptotic upper bound $|A|\le (\frac12+o_t(1))N$.

Round 1 solved only the easy case $t=1$ and gave lower bounds. The most promising Round-2 move is to fully prove the second statement using Elliott's sampling inequality, while keeping the first statement open for $t\ge 2$.

2) Round-1 FOUNDATION USED

I use the following Round-1 results.

1. Equivalent formulation. A set $A\subseteq [N]$ is admissible iff for every integer $d\ge t$, the set of multiples $\{k\ge 1: kd\in A\}$ contains no two consecutive integers.
2. Exact case $t=1$. One has $M_1(N)=\lceil N/2\rceil$.
3. Lower bounds. The odd numbers give $M_t(N)\ge \lceil N/2\rceil$ for every fixed $t$, and for $t=2$ one may improve this by $\Omega(\log N)$ using suitable powers of $2$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is Elliott's sampling inequality, in the form recorded in Tao's notes. It says that an average of an arithmetic function over $[1,N]$ can be approximated, for most small primes $p$, by the corresponding average over the multiples of $p$. Applied to $f=1_A$, this allows us to compare the global density of $A$ with the density of \[ B_p:=\{m\le N/p: pm\in A\}. \] But by the Round-1 reformulation, $B_p$ has no consecutive integers whenever $p\ge t$, and hence has density at most $1/2+O(p/N)$. This immediately forces the global density of $A$ to be at most $1/2+o_t(1)$.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round 1 was the missing upper bound for fixed $t\ge 2$. The plan is:

1. apply Elliott's inequality to $f=1_A$ on $[1,N]$;
2. choose a non-exceptional prime $p\ge t$;
3. transfer the density of $A$ to the density of the compressed set $B_p$ of indices of multiples of $p$ lying in $A$;
4. invoke the no-consecutive-integers bound on $B_p$.

This overcomes the obstruction from Round 1 because the local structure on multiples of a single prime is exactly the kind of one-dimensional condition that the problem forbids.

5) WORK (ROUND-2)

5.1. Setup.

Let \[ \alpha:=\frac{|A|}{N},\qquad f:=1_A,\qquad I=[1,N]. \] Then \[ \frac1N\sum_{n\le N} |f(n)|^2 = \frac{|A|}{N}=\alpha\le 1. \]

5.2. Elliott's inequality.

In the form stated by Tao, there is an absolute constant $C$ such that \[ \sum_{p\le N^{0.1}} \frac1p \left| \frac1N\sum_{n\le N} f(n) - \frac1N\sum_{n\le N} f(n)\,p1_{p\mid n} \right|^2 \le C\,\frac1N\sum_{n\le N}|f(n)|^2 \le C. \] Fix $\varepsilon>0$. Define the exceptional set \[ \mathcal E_\varepsilon:=\left\{p\le N^{0.1}: \left| \frac1N\sum_{n\le N} f(n) - \frac1N\sum_{n\le N} f(n)\,p1_{p\mid n} \right|>\varepsilon\right\}. \] Then the above inequality implies \[ \sum_{p\in \mathcal E_\varepsilon}\frac1p \le \frac{C}{\varepsilon^2}. \]

5.3. Choosing a useful prime.

For fixed $t$ and fixed $\varepsilon$, the harmonic sum of reciprocals of primes in $(t,N^{0.1}]$ tends to infinity with $N$. Hence for all sufficiently large $N$ there exists a prime \[ p\in (t,N^{0.1}]\setminus \mathcal E_\varepsilon. \] For this choice of $p$ we have \[ \left| \alpha- \frac1N\sum_{n\le N}1_A(n)\,p1_{p\mid n} \right| \le \varepsilon. \] Since the multiples of $p$ are exactly $p,2p,\dots,\lfloor N/p\rfloor p$, this becomes \[ \alpha = \frac{p}{N}\,|B_p| + O(\varepsilon), \] where \[ B_p:=\{m\le \lfloor N/p\rfloor: pm\in A\}. \]

5.4. The compressed set $B_p$ has no consecutive integers.

Suppose $m,m+1\in B_p$. Then $pm,p(m+1)\in A$, their difference is $p\ge t$, and \[ p\mid p(m+1). \] This contradicts the defining property of $A$. Therefore $B_p$ contains no two consecutive integers.

If $M:=\lfloor N/p\rfloor$, then any subset of $\{1,\dots,M\}$ with no consecutive integers has size at most $\lceil M/2\rceil\le M/2+1$. Hence \[ |B_p|\le \frac{M}{2}+1 \le \frac{N}{2p}+1. \] Substituting into the previous display gives \[ \alpha \le \frac{p}{N}\left(\frac{N}{2p}+1\right)+O(\varepsilon) = \frac12 + \frac{p}{N}+O(\varepsilon). \] Since $p\le N^{0.1}$, we have $p/N\to 0$. Therefore for every fixed $\varepsilon>0$, \[ \alpha\le \frac12 + O(\varepsilon) \] for all sufficiently large $N$ (with the implied constant absolute).

Because $\varepsilon>0$ was arbitrary, we conclude \[ \frac{|A|}{N}\le \frac12 + o_t(1). \] This proves the second question.

5.5. What remains open.

The exact extremal function \[ M_t(N):=\max\{|A|: A\subseteq [N]\text{ admissible}\} \] is still not determined for fixed $t\ge 2$. The odd numbers still give the lower bound $M_t(N)\ge \lceil N/2\rceil$, and for $t=2$ one can do slightly better by $\Omega(\log N)$. Thus the asymptotic upper bound is now proved, but the exact optimization problem remains open.

6) ADVERSARIAL VERIFICATION

Possible issues checked:

1. Quantifiers. The proof is asymptotic in $N$ for fixed $t$, exactly as required. The prime $p>t$ is chosen only for sufficiently large $N$, which is enough for an $o_t(1)$ statement.
2. Use of Elliott's inequality. The function $f=1_A$ is bounded and square-summable on $[1,N]$, so the inequality applies directly.
3. Compression step. The identity \[ \frac1N\sum_{n\le N}1_A(n)\,p1_{p\mid n} = \frac{p}{N}|B_p| \] is exact, not approximate.
4. No-consecutive bound. This is exactly the Round-1 reformulation specialized to $d=p$.

No hidden assumption was introduced. The proof gives a complete argument for the second question.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The exact extremal problem for $M_t(N)$ remains open for fixed $t\ge 2$, but the second question is now fully proved: \[ |A|\le \left(\frac12+o_t(1)\right)N. \] So the Round-2 status is a genuine correction of the Round-1 draft: the asymptotic upper bound is no longer conjectural.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 80%

9) REFERENCES

1. Erdős Problems, Problem 635.
2. P. D. T. A. Elliott, sampling inequality as quoted in Tao's notes.
3. Terence Tao, 254A, Notes 9 -- second moment and entropy methods, Exercise 8.
4. I. Z. Ruzsa, Erdős and the integers (for historical background on the problem statement).

Erdős Problem #635: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

For fixed $t\ge1$, maximize $|A|$ for $A\subseteq[1,N]$ subject to $(b-a)\nmid b$ whenever $a,b\in A$ and $b-a\ge t$.

All supplied versions considered: 635.tex. The source identifies the correct numbering and proves the already known asymptotic half-density statement using an Elliott inequality. I give an elementary second-moment proof with an explicit error in terms of a prime harmonic sum. The exact extremal function remains open.

2) WORK

Put $\alpha=|A|/N$, $X=\lfloor N^{1/4}\rfloor$, let $\mathcal P=\{p\text{ prime}:t\le p\le X\}$, $P=|\mathcal P|$ and $S=\sum_{p\in\mathcal P}1/p$. Suppose $S>0$. Define \[ U(n)=\sum_{p\in\mathcal P}(1_{p\mid n}-1/p). \] Among multiples of a fixed $p\ge t$, the selected indices cannot be consecutive. Hence at most $N/(2p)+1$ are in $A$, and \[ \sum_{n\in A}U(n)\le N(1/2-\alpha)S+P. \tag{1} \] For uniform $n\in[1,N]$, direct floor-function expansion gives $\mathbb E(1_{p\mid n}-1/p)^2\le1/p$ and, for distinct primes, \[ \left|\mathbb E(1_{p\mid n}-1/p)(1_{q\mid n}-1/q)\right|\le {2\over N}. \] Indeed the three rounding errors have coefficients $1,1/p,1/q$; their sum is at most two. Consequently \[ \mathbb E U^2\le S+3P^2/N. \] Cauchy--Schwarz bounds the absolute value of the left side of $1$ by $N\sqrt{\alpha(S+3P^2/N)}$. Combining and using $\alpha\le1$ gives the explicit bound \[ \alpha\le {1\over2}+{\sqrt{S+3P^2/N}\over S}+{P\over NS}. \] For fixed $t$, the divergence of the sum of reciprocal primes gives $S\to\infty$, while $P^2/N\le N^{-1/2}$. Thus $\alpha\le1/2+o_t(1)$ follows without the quoted sampling theorem. Odd integers supply the matching asymptotic lower density: if $a,b$ are odd and $b-a>0$, their even difference cannot divide the odd number $b$.

3) ADVERSARIAL VERIFICATION

The covariance uses distinct primes so that the common multiples have density $1/(pq)$ up to one rounding unit. The prime cutoff keeps the accumulated rounding error small. The proof treats fixed $t$; it is not uniform for arbitrary $t=t(N)$. It re-proves a known part of the problem, rather than solving the exact question.

4) FINAL

UNRESOLVED. The quantitative second-moment estimate supplies no matching description of the error $M_t(N)-N/2$, nor exact maximizers for $t\ge2$.

5) SOURCES CHECKED

Entire supplied file read. The official indexed page https://www.erdosproblems.com/635 checked on 2026-09-23 confirms that the asymptotic half-density part was already resolved. The proof above is elementary; it does not depend on an unchecked version of Elliott's theorem.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 15%

Problem 635. Classify those triangles which can only be cut into a square number of congruent triangles.

1) [Formal restatement]

A (Euclidean) triangle $T$ is said to admit an $N$-triangle congruent dissection if $T$ can be partitioned into $N$ pairwise congruent triangles (allowing reflections/rotations). The problem asks for a classification of those triangles $T$ such that \[ \{N\ge 1 : T \text{ has an } N\text{-triangle congruent dissection}\}\subseteq \{n^2 : n\in\mathbb{Z}_{\ge 1}\}. \] Equivalently: $T$ can be dissected into congruent triangles only in square cardinalities.

2) [Quick literature/context check (if browsing is available)]

The prompt notes a theorem of Soifer: if the angles and side-lengths of $T$ are both "integrally independent" (in the sense used in that literature), then every congruent-triangle dissection of $T$ has a square number of tiles.

A separate but related line of work studies which $N$ occur at all (Problem 634 below) and which angle configurations force strong arithmetic restrictions on $N$.

No complete classification is known to me from the materials indicated in the prompt; what follows are (i) a fully explicit construction showing that every triangle always has square dissections, and (ii) a structured reduction of the classification problem to obstructions/invariants commonly used in triangle-tiling theory.

3) [Attack plan]

1. Prove explicitly that every triangle can be dissected into $n^2$ congruent triangles for every $n\ge 1$ (this explains why the "square-only" condition is about excluding non-squares).
2. Identify a robust way to encode a congruent-triangle tiling (edge vectors/angle types/boundary word), and list the standard invariants used to force arithmetic restrictions on $N$ (lattice/edge-count equations, Dehn-like invariants, coloring arguments).
3. Explain why a full classification seems to require controlling when such invariants admit non-square solutions.

4) [Work]

4.1. A completely explicit $n^2$-tiling for every triangle.

Let $\triangle ABC$ be any triangle and fix an integer $n\ge 1$.

Let $M$ be the midpoint of segment $BC$. Let $A'$ be the image of $A$ under the half-turn (rotation by $\pi$) about $M$. Then $M$ is the midpoint of both $AA'$ and $BC$, hence the quadrilateral $ABA'C$ is a parallelogram (a quadrilateral whose diagonals bisect each other).

Now subdivide the parallelogram $ABA'C$ into an $n\times n$ grid of congruent parallelograms as follows:

• Divide side $AB$ into $n$ equal segments and draw through the division points the lines parallel to $AC$.
• Divide side $AC$ into $n$ equal segments and draw through the division points the lines parallel to $AB$.

This produces $n^2$ congruent small parallelograms, each a translate of the fundamental cell with side vectors $\frac1n\overrightarrow{AB}$ and $\frac1n\overrightarrow{AC}$.

In each small parallelogram, draw the diagonal parallel to $BC$ (equivalently: the diagonal with direction $\overrightarrow{AC}-\overrightarrow{AB}$). This splits each small parallelogram into two congruent triangles. Therefore the whole parallelogram $ABA'C$ is partitioned into $2n^2$ congruent triangles.

Finally observe that the diagonal $BC$ of the large parallelogram is itself a union of these small diagonals: in the $n\times n$ grid, $BC$ runs along the "anti-diagonal" strip of cells and coincides with the chosen cell-diagonal in each such cell. Hence $BC$ is a union of tile edges, so the half-parallelogram triangle $\triangle ABC$ is a union of whole tiles.

Since $\triangle ABC$ has half the area of the parallelogram and all tiles have equal area, exactly half of the $2n^2$ tiles lie in $\triangle ABC$. Thus $\triangle ABC$ is dissected into precisely $n^2$ congruent triangles.

4.2. What remains for a classification.

The above shows that every triangle has square congruent-triangle dissections. Therefore, to classify "square-only" triangles, one must understand when a triangle admits some non-square congruent-triangle dissection.

A congruent-triangle dissection has two intertwined arithmetic features:

• Angle arithmetic. Each angle of $T$ is a sum of tile angles meeting at boundary vertices. This forces the angles of $T$ to lie in the additive semigroup generated by the tile angles. When the angles of $T$ have strong irrational-independence properties, this can prevent nontrivial angle decompositions.
• Edge-length arithmetic. Along each side of $T$, tile edges appear in some order, giving linear relations between side lengths of $T$ and side lengths of the tile with nonnegative integer coefficients. For triangles with strong linear independence among side lengths, such relations can force very rigid tiling patterns.

In particular, the Soifer condition cited in the prompt (integral independence of both angles and side lengths) is precisely of the type that blocks non-square tilings via these arithmetic constraints.

5) [Verification]

• The $n^2$-construction is checked by: (i) producing $n^2$ congruent parallelogram cells by parallel-line subdivision; (ii) bisecting each cell by a fixed-direction diagonal to get $2n^2$ congruent triangles; (iii) observing the diagonal $BC$ is a union of chosen cell diagonals so the half-parallelogram is tiled; (iv) counting tiles by area to obtain exactly $n^2$.
• No step uses special properties of $\triangle ABC$ beyond being a nondegenerate triangle.

6) [Final]

LABEL: UNRESOLVED
SUBLABEL: Partial progress (explicit $n^2$ tiling) + classification remains open.
I proved constructively that every triangle admits dissections into $n^2$ congruent triangles for every $n\ge 1$ (hence "square-only" means "no non-square tilings"). A complete classification of triangles that forbid all non-square congruent-triangle dissections is not obtained here; the problem reduces to understanding when the standard angle/edge arithmetic constraints admit a non-square solution.

7) [Completion estimate]

About 35% complete: the universal $n^2$-construction is fully proved and the main obstruction mechanisms are laid out, but a full necessary-and-sufficient classification is not reached.