codex 5.2 extra high attempt on Math-5429

Erdős Problem #106

1) FORMAL RESTATEMENT

Let $Q=[0,1]^2$ be the unit square. Place $n$ squares $S_1,\dots,S_n\subset Q$ (rotation allowed) such that \[ \operatorname{int}(S_i)\cap \operatorname{int}(S_j)=\varnothing\quad (i\neq j). \] Write $s_i>0$ for the side length of $S_i$ and define \[ f(n):=\sup \Big\{\sum_{i=1}^n s_i:\; S_1,\dots,S_n\subset Q\text{ squares with pairwise disjoint interiors}\Big\}. \]

Ambiguity check.

The phrase "no common interior point" could mean either (i) pairwise interior-disjoint (as assumed above), or (ii) only that $\bigcap_{i=1}^n \operatorname{int}(S_i)=\varnothing$. The problem text states "it is trivial from Cauchy--Schwarz that $f(k^2)=k$", which is true under (i) via the area bound $\sum s_i^2\le 1$, but is false under (ii) (since squares could overlap heavily). Therefore the intended meaning is (i).

Main question.

For integers $k\ge1$, is it true that \[ f(k^2+1)=k\ ? \]

2) QUICK LITERATURE/CONTEXT CHECK

I only record what the problem text itself states:

• Erdős proved $f(2)=1$.
• Newman proved (as reported) that $f(5)=2$.
• The inequality $f(k^2)=k$ follows from Cauchy--Schwarz.
• Halász gives constructions implying various lower bounds for $f(k^2+t)$.
• A parallel-axis variant $g(n)$ (all squares axis-parallel) is determined exactly in the cited 2024 preprint.

No other results are assumed here.

3) ATTACK PLAN

• Proof track (for $f(k^2+1)=k$): strengthen the area/Cauchy--Schwarz argument by incorporating an additional geometric constraint (e.g. width, boundary length, or a packing/covering inequality) that rules out total side sum $>k$ when only $k^2+1$ squares are present.
• Disproof track: try to beat $k$ by a construction that replaces several $1/k$-tiles by many smaller squares whose side lengths sum to more than the removed tile lengths.

In this writeup I establish the standard universal bounds and constructions; the conjectured matching upper bound remains the first gap.

4) WORK

Lemma 106.1 (area bound).

For any admissible configuration of $n$ squares, \[ \sum_{i=1}^n s_i^2\le 1. \] Proof. The interiors are pairwise disjoint, hence the total area is the sum of the areas: $\sum_i \mathrm{area}(S_i)=\sum_i s_i^2$. Since each $S_i\subset Q$, this total area is at most $\mathrm{area}(Q)=1$. $\square$

Lemma 106.2 (Cauchy--Schwarz upper bound).

For all $n\ge1$, \[ f(n)\le \sqrt{n}. \] Proof. By Cauchy--Schwarz and Lemma 106.1, \[ \sum_{i=1}^n s_i \le \sqrt{n\sum_{i=1}^n s_i^2}\le \sqrt{n\cdot 1}=\sqrt{n}. \] Taking the supremum over all admissible configurations yields $f(n)\le\sqrt{n}$. $\square$

Corollary 106.3 (exact value at perfect squares).

For every integer $k\ge1$, \[ f(k^2)=k. \] Proof. Lemma 106.2 gives $f(k^2)\le\sqrt{k^2}=k$. Conversely, partition $Q$ into a $k\times k$ grid of $k^2$ congruent squares of side $1/k$. Then $\sum s_i = k^2\cdot (1/k)=k$, showing $f(k^2)\ge k$. $\square$

Lemma 106.4 (standard lower bound for $k^2+1$).

For every integer $k\ge1$, \[ f(k^2+1)\ge k. \] Proof. Partition $Q$ into a $k\times k$ grid of $k^2$ tiles of side $1/k$. Keep $k^2-1$ of these tiles as squares of side $1/k$. In the remaining tile (a $1/k\times 1/k$ square), place two disjoint squares of side $1/(2k)$, e.g. one in the lower-left corner and one in the upper-right corner of that tile. This gives $(k^2-1)+2=k^2+1$ squares with total side sum \[ (k^2-1)\cdot\frac1k + 2\cdot\frac1{2k}=\frac{k^2-1}{k}+\frac1k = k. \] Hence $f(k^2+1)\ge k$. $\square$

Lemma 106.5 (monotonicity of $f$).

The function $f(n)$ is nondecreasing in $n$: for every $n\ge1$, \[ f(n+1)\ge f(n). \] Proof. Fix $\varepsilon>0$ and choose an admissible configuration of $n$ squares with total side sum $>f(n)-\varepsilon$. Shrink each square about its center by a factor $(1-\delta)$, where $\delta>0$ is small enough that the new total side sum is $>(f(n)-\varepsilon)-\varepsilon$. Shrinking preserves interior-disjointness and keeps all squares inside $Q$. The total area strictly decreases, so the complement of the union of the shrunken closed squares is a nonempty open subset of $Q$. Any nonempty open subset of $\mathbb R^2$ contains a (small) square; place an additional square $S_{n+1}$ in that open region. The resulting $(n+1)$-square configuration has total side sum $>f(n)-2\varepsilon$. Letting $\varepsilon\to0$ yields $f(n+1)\ge f(n)$. $\square$

5) VERIFICATION (FAST REALITY CHECK)

• $n=1$: clearly $f(1)=1$ (take $S_1=Q$). Lemma 106.2 gives $f(1)\le1$.
• $n=2$: Lemma 106.2 gives $f(2)\le\sqrt2\approx1.414$; the problem text states Erdős proved $f(2)=1$.
• $n=4$ ($k=2$): Corollary 106.3 gives $f(4)=2$.
• $n=5$ ($k=2$): Lemma 106.4 gives $f(5)\ge2$; the problem text states $f(5)=2$.

All inequalities above are consistent with these small cases.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. For all $n$, $f(n)\le\sqrt{n}$ (Lemma 106.2); for all $k$, $f(k^2)=k$ (Corollary 106.3) and $f(k^2+1)\ge k$ (Lemma 106.4).

(ii) Exact first gap. To prove $f(k^2+1)=k$, it suffices to prove the missing upper bound \[ f(k^2+1)\le k\qquad(k\ge1), \] which is stronger than the universal bound $f(k^2+1)\le\sqrt{k^2+1}$.

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

1. Prove a geometric inequality upgrading $\sum s_i^2\le1$ by adding a second constraint (e.g. involving total boundary length or projection widths) that forces $\sum s_i\le k$ when $n\le k^2+1$.
2. Classify "near-extremal" configurations for $f(k^2)$ and show any attempt to insert one more square forces a loss in total side sum.
3. Search (by computer) for $k=2,3$ for configurations of $k^2+1$ squares with sum $>k$ to test plausibility and identify extremal patterns.

(iv) Minimal counterexample structure. A counterexample for some $k$ would be a packing of $k^2+1$ interior-disjoint squares in $Q$ with $\sum s_i>k$. Such a configuration cannot rely on many extremely tiny squares (which add little to the sum) and would need a highly non-grid-like arrangement of moderately sized squares.