Erdős Problem #106

FORMAL RESTATEMENT

QUICK LITERATURE AND CONTEXT CHECK

OBJECTIVE AND ATTACK PLAN

WORK

Containment and non-overlap certificate

Substitution of $2$ in $3$--$4$ places all $68$ vertices in $[0,1]^2$, so convexity proves containment. Among squares $1$ through $16$, the rectangular coordinate intervals in $3$ separate every pair in at least one coordinate. For their pairs with square $17$, the following table lists a sufficient vector. Set $v_1=(1,0)$, $v_2=(0,1)$, $v_3=(C,S)$, $v_4=(-S,C)$. \[ \begin{array}{c|rrrrrrrrrrrrrrrr} i&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline \text{index of separating vector for }(i,17) &1&1&1&1&2&2&3&2&2&1&1&4&2&1&1&1 \end{array} \tag{5} \] All comparisons in this certificate are rational. The two tilted contacts are pinned by the exact identities \[ \begin{aligned} a(C+4S)+uC\left(3-\frac S{C+S}\right)&=C+\frac74S,\\ a(-2S-3C)+u\left(5S+2C+\frac{C^2}{C+S}\right)&=-\frac34C. \end{aligned} \tag{6} \] They can alternatively be used to derive the values of $a,u$ in $2$. An independent offline audit evaluated every vertex and every one of the $\binom{17}2=136$ separating comparisons with exact fractions. Equations $2$--$5$ specify the finite certificate in full, so the packing does not depend on a numerical picture-based assertion.

The strict gain and its propagation

It also supplies counterexamples for every integer $k\geq4$. Given any packing of $k^2+1$ squares, shrink it by $k/(k+1)$ into the lower-left square of that side. Tile the remaining L-shaped border by $2k+1$ squares of side $1/(k+1)$. The new number of squares is $(k+1)^2+1$, and taking suprema of the side sums yields \[ f((k+1)^2+1)\geq\frac{k}{k+1}f(k^2+1)+\frac{2k+1}{k+1}. \] Writing $\delta_k=f(k^2+1)-k$, this says $(k+1)\delta_{k+1}\geq k\delta_k$. In particular $\delta_k\geq4\delta_4/k>0$ for $k\geq4$, and the sum of these excesses diverges. This border argument is valid for a supremum as well as for an attained optimum.

VERIFICATION AND SCOPE

SOURCES

• Current statement and attribution: https://www.erdosproblems.com/106.
• Primary construction and certificate: https://github.com/Sprite143/erdos-106-counterexample, especially CONSTRUCTION.md and CERTIFICATE_n17.json.

CONCLUSION

Draw $n$ squares inside the unit square with no common interior point. Let $f(n)$ be the maximum possible sum of the side-lengths of the squares. Is $f(k^2+1)=k$? In [Er94b] Erdős dates this conjecture to 'more than 60 years ago'. Erdős proved that $f(2)=1$ in an early mathematical paper for high school students in Hungary. Newman proved (in personal communication to Erdős) that $f(5)=2$. It is trivial from the Cauchy-Schwarz inequality that $f(k^2)=k$. Erdős also asks for which $n$ is it true that $f(n+1)=f(n)$. It is easy to see that $f(k^2+1)\geq k$, by first dividing the unit square into $k^2$ smaller squares of side-length $1/k$, and then replacing one square by two smaller squares of side-length $1/2k$. Halász [Ha84] gives a construction that shows $f(k^2+2)\geq k+\frac{1}{k+1}$, and in general, for any $c\geq 1$,\[f(k^2+2c+1)\geq k+\frac{c}{k}\]and\[f(k^2+2c)\geq k+\frac{c}{k+1}.\]Halász also considers the variants where we replace a square by a parallelogram or triangle. Erdős and Soifer [ErSo95] and Campbell and Staton [CaSt05] have conjectured that, in general, for any integer $-k<c<k$, $f(k^2+2c+1)=k+\frac{c}{k}$, and proved the corresponding lower bound. Praton [Pr08] has proved that this general conjecture is equivalent to $f(k^2+1)=k$. Baek, Koizumi, and Ueoro [BKU24] have proved $g(k^2+1)=k$, where $g(\cdot)$ is defined identically to $f(\cdot)$ with the additional assumption that all squares have sides parallel to the sides of the unit square. More generally, they prove that $g(k^2+2c+1)=k+c/k$ for any $-k<c<k$, which determines all values of $g(\cdot)$. References [BKU24] Baek, J. and Koizumi, J. and Ueoro, T., A note on the Erdős conjecture about square packing . arXiv:2411.07274 $2024$. [CaSt05] Campbell, Connie and Staton, William, A square-packing problem of Erdős . Amer. Math. Monthly $2005$, 165--167. [Er94b] Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry . Math. Pannon. $1994$, 261-269. [ErSo95] Erdős, Paul and Soifer, Alexander, Squares in a square . Geombinatorics $1995$, 110--114. [Ha84] Halász, Sylvia, Packing a convex domain with similar convex domains . J. Combin. Theory Ser. A $1984$, 85--90. [Pr08] Praton, I., Packing squares in a square . Math. Mag. $2008$, 358-361.

OUTPUT 1) FORMAL RESTATEMENT Let $U=[0,1]^2$ be the unit square.

A (closed) square $S\subseteq U$ has a side-length $s(S)>0$ (no restriction on orientation). A family of squares $S_1,\dots,S_n\subseteq U$ is admissible if their interiors are pairwise disjoint: \[\operatorname{int}(S_i)\cap\operatorname{int}(S_j)=\emptyset\quad\text{for all }i\neq j.\]

Define \[f(n):=\sup\left\{\sum_{i=1}^n s(S_i):\; S_1,\dots,S_n\subseteq U\text{ admissible}\right\}. \] (The problem statement phrases this as a maximum; using $\sup$ avoids an attainment issue.)

Main conjecture asked in the problem block: \[\forall k\in\mathbb N:\quad f(k^2+1)=k\,?\]

Secondary question asked in the problem block: Determine for which $n$ one has $f(n+1)=f(n)$.

2) QUICK LITERATURE/CONTEXT CHECK Web browsing available: YES, but in this write-up I do not use external sources. I only rely on statements already present in the PROBLEM block.

3) ATTACK PLAN The trivial global bound is the area/Cauchy--Schwarz inequality: \[\sum s(S_i)^2\le 1\implies \sum s(S_i)\le \sqrt n.\] This immediately yields $f(k^2)=k$ (sharp via the $k\times k$ grid construction).

To prove $f(k^2+1)=k$ one needs a strict improvement over $\sqrt{k^2+1}$, i.e. show that the geometric constraints beyond area force $\sum s(S_i)\le k$. I do not complete such an argument here.

4) WORK FAST REALITY CHECK (small cases / sanity checks) - $n=1$: One square of side $1$ fills $U$, so $f(1)=1$. - $n=4$: Partition $U$ into a $2\times 2$ grid of side $1/2$ squares. Sum of side-lengths $=4\cdot(1/2)=2$. The general upper bound (Lemma 4.2 below) gives $f(4)\le\sqrt 4=2$, hence $f(4)=2$. - $n=5$: Taking $k=2$ in Lemma 4.5 gives an explicit packing with total side-length $2$, so $f(5)\ge 2$, consistent with the problem text claim $f(5)=2$.

Lemma 4.1 (Area bound). For any admissible squares $S_1,\dots,S_n\subseteq U$, \[\sum_{i=1}^n s(S_i)^2\le 1.\]

Proof. Each square $S_i$ has area $\operatorname{area}(S_i)=s(S_i)^2$. Because the interiors are pairwise disjoint, the squares overlap (if at all) only on boundaries, which have area $0$. Therefore the area of the union is the sum of the areas: \[\operatorname{area}\left(\bigcup_{i=1}^n S_i\right)=\sum_{i=1}^n \operatorname{area}(S_i)=\sum_{i=1}^n s(S_i)^2.\] Since $\bigcup_i S_i\subseteq U$ and $\operatorname{area}(U)=1$, we get $\sum_i s(S_i)^2\le 1$. $\square$

Lemma 4.2 (Cauchy--Schwarz upper bound). For any admissible squares $S_1,\dots,S_n\subseteq U$, \[\sum_{i=1}^n s(S_i)\le \sqrt n.\] Consequently $f(n)\le \sqrt n$ for all $n$.

Proof. Apply Cauchy--Schwarz to the vectors $(s(S_1),\dots,s(S_n))$ and $(1,\dots,1)$: \[(\sum_{i=1}^n s(S_i))^2\le (\sum_{i=1}^n 1^2)(\sum_{i=1}^n s(S_i)^2)=n\sum_{i=1}^n s(S_i)^2.\] By Lemma 4.1, $\sum_i s(S_i)^2\le 1$, hence \[(\sum_i s(S_i))^2\le n\quad\Rightarrow\quad \sum_i s(S_i)\le\sqrt n.\] Taking the supremum over admissible families gives $f(n)\le\sqrt n$. $\square$

Corollary 4.3 (Exact value at perfect squares). For every integer $k\ge 1$, \[f(k^2)=k.\]

Proof. Upper bound: Lemma 4.2 gives $f(k^2)\le\sqrt{k^2}=k$. Lower bound: Lemma 4.4 constructs an admissible family with sum $k$, so $f(k^2)\ge k$. Hence equality. $\square$

Lemma 4.4 ($k\times k$ grid construction). For every integer $k\ge 1$ there is an admissible family of $k^2$ squares in $U$ with total side-length exactly $k$.

Proof. Partition $U$ into a $k\times k$ grid of congruent axis-parallel squares, each of side $1/k$. These $k^2$ squares have disjoint interiors and cover $U$. Their total side-length is \[k^2\cdot\frac{1}{k}=k.\] $\square$

Lemma 4.5 (Elementary lower bound at $k^2+1$). For every integer $k\ge 1$, \[f(k^2+1)\ge k.\]

Proof. Start from the $k\times k$ grid in Lemma 4.4 (total side-length $k$). Pick one of the $k^2$ grid squares of side $1/k$. Replace it by two smaller axis-parallel squares of side $1/(2k)$ placed side-by-side inside that grid cell. This keeps interiors disjoint and contained in $U$.

The new family has $(k^2-1)+2=k^2+1$ squares and total side-length \[(k^2-1)\cdot\frac{1}{k} + 2\cdot\frac{1}{2k} = \frac{k^2-1}{k}+\frac{1}{k}=k.\] So $f(k^2+1)\ge k$. $\square$

5) VERIFICATION - Lemma 4.1 uses only additivity of area up to measure-zero boundaries. - Lemma 4.2 uses Cauchy--Schwarz and Lemma 4.1. - Lemma 4.5: the replacement increases the count by $+1$ while preserving total side-length exactly; the two $1/(2k)$ squares fit inside the removed $1/k$-square because $2\cdot(1/(2k))=1/k$.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result obtained here. - For all $n$, $f(n)\le \sqrt n$ (Lemma 4.2). - For all $k\ge 1$, $f(k^2)=k$ (Corollary 4.3). - For all $k\ge 1$, $f(k^2+1)\ge k$ (Lemma 4.5).

(ii) Exact first gap. Show the matching upper bound $f(k^2+1)\le k$ for all integers $k\ge 1$. Equivalently: rule out any admissible packing of $k^2+1$ squares in $U$ with \[\sum_{i=1}^{k^2+1} s(S_i) > k.\]

(iii) Top 3 next moves (concrete targets). 1. Prove a stability refinement of Lemma 4.2 at $n=k^2+1$: if $\sum s(S_i)$ is close to $k$, then many squares must have side close to $1/k$. Try to make this quantitative. 2. Use that $k^2+1$ squares force at least two squares to fall in the same cell of a $k\times k$ coarse partition; attempt to convert this to a strict upper bound on total side-length via a local packing inequality inside one cell. 3. Attempt a linear-programming / interval-projection bound: choose a direction $\theta$ and bound total projected lengths of the squares along $\theta$ by the projection length of $U$; optimize over $\theta$ and use the fact that a square's projection length depends on its orientation.

(iv) Minimal counterexample structure (if the conjecture is false). A smallest $k\ge 1$ for which there exists an admissible family of $k^2+1$ (non-degenerate) squares inside $U$ whose total side-length exceeds $k$. Such a counterexample would necessarily beat the trivial area bound by a $\Theta(1/k)$ margin, i.e. have $\sum s(S_i)\in (k,\sqrt{k^2+1}]$.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - We work in the Euclidean plane. The unit square is $[0,1]\times[0,1]$. - A square means a (possibly rotated) closed square region with positive side length. - "No common interior point" is interpreted as: the interiors of the $n$ squares are pairwise disjoint, i.e. no point lies in the interior of two distinct squares. (Equivalently, the interiors form a packing.)

For $n\ge 1$, define $f(n)$ to be the supremum (or maximum, if attained) of \[\sum_{i=1}^n s_i\] over all collections of $n$ squares contained in the unit square with pairwise disjoint interiors, where $s_i$ is the side length of the $i$th square.

Question. Is it true that for every integer $k\ge 1$, \[f(k^2+1)=k?\] Also: for which $n$ does $f(n+1)=f(n)$ hold?

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. I only use information stated in the problem text (e.g. that $f(k^2)=k$ is trivial by Cauchy--Schwarz, and that the conjecture $f(k^2+1)=k$ is open).

3) ATTACK PLAN Proof track ideas: 1. Use area: disjoint interiors imply $\sum s_i^2\le 1$, giving strong universal upper bounds on $\sum s_i$. 2. Try to sharpen the area-only bound in the special case $n=k^2+1$ by exploiting that $k^2$ squares already tile optimally, leaving no area slack.

Disproof track ideas: 1. Try to build packings with $k^2+1$ squares whose side-length sum exceeds $k$ (the text mentions many lower bounds of this type for $k^2+2c$ and $k^2+2c+1$).

Chosen path in this attempt: establish the area/Cauchy--Schwarz upper bound rigorously and derive the exact value $f(k^2)=k$, and record the simple lower bound $f(k^2+1)\ge k$.

4) WORK Lemma 1 (Area bound). If $n$ squares of side lengths $s_1,\dots,s_n$ are placed inside the unit square with pairwise disjoint interiors, then \[\sum_{i=1}^n s_i^2 \le 1.\]

Proof. The area of the $i$th square is $s_i^2$. Since the interiors are pairwise disjoint and all squares lie inside the unit square (area $1$), the sum of their areas is at most $1$: \[\sum_{i=1}^n s_i^2 \le 1.\square\]

Lemma 2 (Cauchy--Schwarz upper bound on total side length). Under the same hypotheses, \[\sum_{i=1}^n s_i \le \sqrt{n}.\] In particular, $f(n)\le \sqrt n$ for all $n$.

Proof. By Cauchy--Schwarz, \[\left(\sum_{i=1}^n s_i\right)^2 \le \left(\sum_{i=1}^n 1^2\right)\left(\sum_{i=1}^n s_i^2\right)=n\sum_{i=1}^n s_i^2.\] By Lemma 1, $\sum s_i^2\le 1$, hence $(\sum s_i)^2\le n$, i.e. $\sum s_i\le \sqrt n$. Taking the supremum over all packings shows $f(n)\le \sqrt n$. $\square$

Lemma 3 (Exact value $f(k^2)=k$). For every integer $k\ge 1$, \[f(k^2)=k.\]

Proof. Upper bound: apply Lemma 2 with $n=k^2$ to get $f(k^2)\le \sqrt{k^2}=k$.

Lower bound: partition the unit square into a $k\times k$ grid of $k^2$ axis-parallel squares, each of side length $1/k$. These squares have disjoint interiors and are contained in the unit square, and their side lengths sum to $k^2\cdot(1/k)=k$. Thus $f(k^2)\ge k$.

Combining both bounds gives $f(k^2)=k$. $\square$

Lemma 4 (Simple lower bound for $k^2+1$ squares). For every integer $k\ge 1$, \[f(k^2+1)\ge k.\]

Proof. Start from the $k^2$-square grid packing from Lemma 3, with each square of side length $1/k$. Remove one of these squares and replace it by two axis-parallel squares of side length $1/(2k)$ placed inside the removed square (e.g. side-by-side). This yields $(k^2-1)+2=k^2+1$ squares with disjoint interiors in the unit square. The total side-length sum is \[(k^2-1)\cdot\frac1k + 2\cdot\frac1{2k} = \frac{k^2-1}{k} + \frac{1}{k}=k.\] Therefore $f(k^2+1)\ge k$. $\square$

Lemma 5 (Monotonicity). The function $f(n)$ is nondecreasing: $f(n+1)\ge f(n)$ for all $n\ge 1$.

Proof. Take any packing of $n$ squares in the unit square with total side-length sum within $\varepsilon>0$ of $f(n)$. Place an additional square of side length $\delta>0$ (very small) in a corner region of the unit square not intersecting the interiors of the existing squares; this is possible by choosing $\delta$ small enough. Then we obtain a packing of $n+1$ squares with total side-length sum increased by $\delta$. Letting $\delta\downarrow 0$ and then $\varepsilon\downarrow 0$ shows $f(n+1)\ge f(n)$. $\square$

FAST REALITY CHECK - For $k=1$, Lemma 3 gives $f(1)=1$ and Lemma 4 gives $f(2)\ge 1$; Lemma 2 gives $f(2)\le \sqrt2$ (so $f(2)=1$ is plausible, as stated in the problem text). - For $k=2$, Lemma 3 gives $f(4)=2$ and Lemma 4 gives $f(5)\ge 2$; Lemma 2 gives $f(5)\le \sqrt5\approx 2.236$ (consistent with $f(5)=2$ stated in the text).

5) VERIFICATION - Lemmas 1--2 use only disjointness of interiors and total area $\le 1$. - Lemma 3 is tight because the grid construction saturates the area bound with equal squares, where Cauchy--Schwarz has equality. - Lemma 4 uses an explicit packing modification and preserves disjoint interiors by nesting inside one square.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved the universal upper bound $f(n)\le \sqrt n$ and the exact value $f(k^2)=k$ (Lemmas 2--3), and the easy lower bound $f(k^2+1)\ge k$ (Lemma 4).

(ii) First gap: Prove the matching upper bound $f(k^2+1)\le k$ (or construct a packing with sum $>k$). Area/Cauchy--Schwarz alone only gives $f(k^2+1)\le \sqrt{k^2+1}=k+O(1/k)$, which is too weak.

(iii) Top 3 next moves (concrete): 1. Seek a refinement of Lemma 1 that uses not only area but also boundary/packing constraints (e.g. by integrating projections) to upper bound $\sum s_i$ when $n=k^2+1$. 2. Analyze equality cases of the Cauchy--Schwarz bound: for $n=k^2+1$, equality is impossible, so quantify the inevitable slack in $\sum s_i$ given $\sum s_i^2\le 1$ and geometric packing constraints. 3. Attempt to optimize explicit constructions for $k^2+1$ squares (beyond the "split one square" construction) and see whether any arrangement can push the sum above $k$ for small $k$.

(iv) What a minimal counterexample would likely look like (structure/parameters): For some fixed $k$, a packing of $k^2+1$ squares in the unit square with total side-length sum $k+\delta$ for some $\delta>0$, meaning the packing uses non-equal square sizes in a way that beats the naive "grid + split" construction while still respecting the tight area constraint.