Erdős Problem #624

Erdős Problem 624 --- ROUND-2

1) ROUND-2 OBJECTIVE

Path pursued: (C) obstruction / gap-isolation.

Round-1 gave only lower-bound information: the counting lower bound $H(n)\ge \log_2 n$, Alon's argument that $H(2^k)\ge k+1$, and the observation that fixed-size collision arguments leave too much slack when $h=\log_2 n + C$. In this round I do two things:

• I prove a barrier theorem showing that a broad class of first-moment / averaging arguments can never beat the trivial bound $n\le 2^h$.
• I prove a new unconditional upper bound \[ H(n)\le \log_2 n + 2\log_2\log_2 n + O(1), \] which is strictly stronger than the Round-1 quoted $(3+o(1))\log_2\log_2 n$ upper bound.

So Round-2 both sharpens the obstruction on the lower-bound side and advances the upper-bound side.

2) Round-1 FOUNDATION USED

I use the following Round-1 results as fixed background:

• the restatement of $H(n)$;
• the basic counting lower bound $H(n)\ge \lceil\log_2 n\rceil$;
• Alon's argument that $H(2^k)\ge k+1$;
• the Round-1 diagnosis that the naive "many collisions in one fibre" idea does not by itself force an unbounded additive gap.

3) NEW INSIGHT / TOOL (ROUND-2)

There are two new tools.

• Boolean-lattice colouring viewpoint. A witness $f:\mathcal P(X)\to X$ is exactly an $n$-colouring of the Boolean lattice $2^X$ such that every principal ideal $2^Y$ with $|Y|=h$ is rainbow.

• Random-colouring upper bound plus an LP/first-moment barrier. The random-colouring argument yields the upper bound $H(n)\le \log_2 n + 2\log_2\log_2 n + O(1)$. Separately, any lower-bound argument obtained by taking nonnegative linear combinations of the basic surjectivity inequalities for $h$-sets collapses to the trivial counting bound $n\le 2^h$.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round-1 was:

How can one go beyond the trivial bound $n\le 2^h$ and the constant-gap argument $H(2^k)\ge k+1$?

Round-2 attacks this in two directions.

1. Prove that the most obvious first-moment averaging strategy is provably incapable of giving anything stronger than $n\le 2^h$.
2. Compensate by strengthening the known upper bound through a direct random construction.

This does not solve the original problem, but it cleanly separates what still needs to happen: any eventual proof of $H(n)-\log_2 n\to\infty$ must use structure beyond these first-moment inequalities.

5) WORK (ROUND-2)

Reformulation.

Let $X$ be an $n$-element set, and let $h$ be such that there exists $f:\mathcal P(X)\to X$ with the property that every $Y\subseteq X$ of size $h$ satisfies \[ \{f(A):A\subseteq Y\}=X. \] For each $x\in X$, define \[ \mathcal F_x:=\{A\subseteq X:f(A)=x\}. \] Then $(\mathcal F_x)_{x\in X}$ is a partition of $\mathcal P(X)$, and the defining property of $H(n)$ is:

for every $x\in X$ and every $Y\in \binom{X}{h}$, there exists $A\in \mathcal F_x$ with $A\subseteq Y$.

Equivalently, each colour class $\mathcal F_x$ hits every principal ideal $2^Y$ with $|Y|=h$.

Barrier theorem (first-moment / averaging methods).

Fix $h$. For each $x\in X$ and $Y\in \binom{X}{h}$ we have the basic surjectivity inequality \[ \sum_{A\subseteq Y}\mathbf 1_{\{f(A)=x\}}\ge 1. \tag{1} \] Take any family of nonnegative coefficients $(c_Y)_{Y\in \binom{X}{h}}$ that do not depend on $x$. Multiply $1$ by $c_Y$ and sum over all $Y\in \binom{X}{h}$. For a fixed $x$, this gives \[ \sum_{A\subseteq X}\left(\sum_{\substack{Y\in \binom{X}{h}\\ A\subseteq Y}} c_Y\right)\mathbf 1_{\{f(A)=x\}} \ \ge\ \sum_{Y\in \binom{X}{h}} c_Y. \tag{2} \] Now sum $2$ over all $x\in X$. Because the sets $\mathcal F_x$ partition $\mathcal P(X)$, each subset $A\subseteq X$ contributes exactly once. Hence \[ n\sum_{Y\in \binom{X}{h}} c_Y \le \sum_{Y\in \binom{X}{h}} c_Y\sum_{A\subseteq Y}1 = 2^h\sum_{Y\in \binom{X}{h}} c_Y. \] If not all $c_Y$ vanish, we may divide by the positive scalar $\sum_Y c_Y$ and obtain \[ n\le 2^h. \]

Therefore:

Any lower-bound argument that is obtained solely by taking nonnegative linear combinations of the basic inequalities $1$, with coefficients independent of the colour $x$, can recover at most the trivial counting bound $n\le 2^h$.

This rigorously rules out an entire first-moment class of approaches.

New upper bound.

I now prove \[ H(n)\le \log_2 n + 2\log_2\log_2 n + O(1). \]

Theorem.

For all sufficiently large $n$, \[ H(n)\le \left\lceil \log_2 n + 2\log_2\log_2 n + 2\right\rceil. \]

Proof.

Let $X$ be an $n$-element set, and put \[ L:=\log_2 n,\qquad h:=\left\lceil L+2\log_2 L+2\right\rceil. \] Choose a random map $f:\mathcal P(X)\to X$ by assigning to each subset $A\subseteq X$ an independent uniformly distributed value $f(A)\in X$.

Fix $x\in X$ and $Y\in \binom{X}{h}$. The event that $x$ is missing from the image $\{f(A):A\subseteq Y\}$ is exactly the event that all $2^h$ subsets of $Y$ avoid the value $x$, and therefore has probability \[ \Pr\left(x\notin \{f(A):A\subseteq Y\}\right) = \left(1-\frac1n\right)^{2^h} \le e^{-2^h/n}. \] By the union bound, the probability that some pair $(x,Y)$ is bad is at most \[ n\binom{n}{h}e^{-2^h/n}. \tag{3} \] So it is enough to show that the quantity in $3$ is $<1$.

Now $h\le 2L$ for all sufficiently large $n$. Using the standard bound $\binom{n}{h}\le (en/h)^h$, we get \[ \ln\!\left(n\binom{n}{h}\right) \le \ln n + h\ln\!\left(\frac{en}{h}\right) \le \ln n + 2L(\ln n+1) = 2(\ln 2)L^2 + O(L). \tag{4} \] Here the last inequality uses only $h\le 2L$ and the elementary bound $\ln(en/h)\le \ln n+1$. On the other hand, by the definition of $h$, \[ \frac{2^h}{n}\ge 4L^2. \tag{5} \] Since $4>2\ln 2$, the right-hand side of $5$ is larger than the right-hand side of $4$ for all sufficiently large $n$. Hence \[ \ln\!\left(n\binom{n}{h}\right) < \frac{2^h}{n}, \] which implies \[ n\binom{n}{h}e^{-2^h/n}<1. \] Therefore the bad-event probability in $3$ is strictly less than $1$, so there exists a map $f:\mathcal P(X)\to X$ for which no pair $(x,Y)$ is bad.

Thus every $h$-subset $Y$ satisfies $\{f(A):A\subseteq Y\}=X$, and therefore \[ H(n)\le h=\left\lceil \log_2 n + 2\log_2\log_2 n + 2\right\rceil \] for all sufficiently large $n$. $\square$

Corollary.

\[ H(n)\le \log_2 n + (2+o(1))\log_2\log_2 n. \]

This is strictly stronger than the Round-1 quoted upper bound \[ H(n)<\log_2 n + (3+o(1))\log_2\log_2 n. \]

6) ADVERSARIAL VERIFICATION

• Do larger sets $Y$ with $|Y|>h$ also work? Yes. If every $h$-subset sees all colours, then every larger set does too, since it contains an $h$-subset.

• Did the random proof use independence correctly? Yes. For a fixed pair $(x,Y)$, the values $\{f(A):A\subseteq Y\}$ are independent by construction, so the missing-colour probability is exactly $(1-\frac1n)^{2^h}$.

• Is the barrier theorem too strong? No. It is intentionally limited: it rules out only the class of arguments obtained from nonnegative linear combinations of the elementary inequalities $1$ with coefficients independent of the colour. It does not rule out more sophisticated multi-colour or higher-order arguments. Indeed, Alon's $H(2^k)\ge k+1$ argument from Round-1 already lies outside this purely first-moment framework.

• Does the new upper bound contradict the conjectured lower bound? No. The original problem asks whether $H(n)-\log_2 n\to\infty$. The theorem above merely shows that the excess above $\log_2 n$ is at most $2\log_2\log_2 n+O(1)$. The conjectured divergence could still hold inside that window.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round-2 gives two genuine advances beyond Round-1:

1. a new unconditional upper bound \[ H(n)\le \log_2 n + 2\log_2\log_2 n + O(1), \] which improves the Round-1 quoted $(3+o(1))\log_2\log_2 n$ upper bound;

2. a rigorous barrier theorem showing that a broad first-moment / averaging class of lower-bound arguments can never beat the trivial bound $n\le 2^h$.

So the unresolved part of Problem 624 is now sharper: to prove $H(n)-\log_2 n\to\infty$, one needs a genuinely structural lower-bound mechanism.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

• T. F. Bloom, Erdős Problem #624, erdosproblems.com/624, accessed 2026-03-07.

10) OUTPUT FORMAT

This section is written in drop-in LaTeX form and starts directly from \section{}, with no preamble.

Erdős Problem #624: independent continuation

Date: 23 September 2026. Source versions read in full: 624.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

The target is $H(n)-\log_2 n\to\infty$, where every Boolean ideal $2^Y$ of rank at least $H(n)$ must receive all $n$ colours. The supplied random-colouring upper bound does not address this lower-bound target. Surjectivity is required, not a rainbow colouring unless $2^{|Y|}=n$.

2) AN INTEGRAL OBSTRUCTION

Suppose $n=2^h$, $h\ge2$, and rank $h$ suffices. Each ideal $2^Y$ has exactly $n$ members, so its colours must all be distinct. Every two distinct members of \[ \{\varnothing\}\cup\{\{x\}:x\in X\} \] are contained in some such ideal, since their union has size at most two. Hence these $n+1$ sets must have different colours, a contradiction. Thus $H(2^h)\ge h+1$. This is only a weak, already known consequence, not the desired divergent excess; the official discussion records substantially stronger results of Alon.

3) WHY THE NATURAL LINEAR RELAXATION STALLS

Introduce assignment variables $x_{A,c}\ge0$, with \[ \sum_c x_{A,c}=1,\qquad \sum_{A\subseteq Y}x_{A,c}\ge1 \quad(|Y|=h,\ c\in X). \] An actual colouring is a zero-one solution. But the fractional assignment $x_{A,c}=1/n$ is feasible whenever $2^h\ge n$. Conversely summing the covering inequalities for one $Y$ gives $2^h\ge n$. Therefore this relaxation has exactly the trivial logarithmic threshold. No argument using only linear consequences of these inequalities can prove a stronger lower bound: the explicit fractional witness would contradict it.

4) NEXT STEP AND LIMITATION

The integral argument uses simultaneous incompatibility across overlapping ideals, a feature absent from that relaxation. A useful next target is a quantitative inequality bounding the number of repeated colours forced inside one ideal when $n$ is just below $2^h$. The argument above forces one repetition only at equality and does not amplify it as $h$ grows.

7) FINAL

UNRESOLVED. The contribution is a transparent integrality barrier and a self-contained weak lower bound, with no claimed advance over the strongest known bounds. Reference checked: https://www.erdosproblems.com/forum/thread/624.

8) COMPLETION ESTIMATE

COMPLETION: 5% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem 624

FORMAL RESTATEMENT

Let $X$ be a finite set with $|X|=n$. Define $H(n)$ to be the least integer $h$ for which there exists a function \[ f:\mathcal P(X)\to X \] such that for every subset $Y\subseteq X$ with $|Y|\ge h$ we have \[ \{f(A):A\subseteq Y\}=X. \] Equivalently, for every $Y\subseteq X$ with $|Y|=h$, the restriction $f\!\restriction\mathcal P(Y)$ is surjective onto $X$.

The problem asks to prove that \[ H(n)-\log_2 n\to\infty\qquad (n\to\infty). \]

QUICK LITERATURE/CONTEXT CHECK

This is Erdős Problem #624 and is listed as open. Erdős--Hajnal proved \[ \log_2 n\le H(n) < \log_2 n + (3+o(1))\log_2\log_2 n. \] A folklore "first step" is to show $H(2^k)\ge k+1$. A short argument attributed to Alon establishes this. More strongly, the Erdős Problems page records (attribution to Alon, personal communication) that for $n=2^k$ and any $f$, there exists $Y$ with $|Y|=k$ such that $\#\{f(A):A\subseteq Y\}<(1-c)2^k$ for some absolute $c>0$ and $k$ large.

ATTACK PLAN

1. Re-derive the basic lower bound $H(n)\ge\log_2 n$ (counting).
2. Present Alon's argument showing $H(2^k)\ge k+1$.
3. Explore whether the collision idea can be iterated (using many $t$-subsets with identical image) to force $H(2^k)\ge k+\omega(1)$, which would imply the desired limit. Identify precisely where the iteration fails.

WORK

(A) The easy information-theoretic lower bound $H(n)\ge\log_2 n$.

Fix $h$ and suppose there exists $f$ satisfying the defining property for $H(n)$ with this $h$. Take any $Y\subseteq X$ with $|Y|=h$. Then $\mathcal P(Y)$ has $2^h$ subsets, so the image $\{f(A):A\subseteq Y\}$ has size at most $2^h$. But by requirement it equals $X$, so has size $n$. Hence $n\le 2^h$, i.e. \[ h\ge \log_2 n. \] Therefore $H(n)\ge\lceil\log_2 n\rceil$.

(B) Alon's argument for $H(2^k)\ge k+1$.

Let $n=2^k$ and let $X$ be a set of size $n$. Consider an arbitrary function $f:\mathcal P(X)\to X$. By the pigeonhole principle, among the ${n\choose 2}$ two-element subsets of $X$, some value $x\in X$ is attained by at least \[ \frac{{n\choose 2}}{n} = \frac{n-1}{2} \] of them. Let $A_1,\dots,A_m$ (with $m\ge\frac{n-1}{2}$) be distinct $2$-subsets with $f(A_i)=x$.

Now take any $k$-element subset $Y\subseteq X$ that contains at least $\lfloor k/2\rfloor$ of the sets $A_i$ (i.e. contains both elements of each of these $A_i$). For each such $A_i\subseteq Y$, the subset $A_i$ contributes no new image value beyond $x$. Thus the number of distinct images on $\mathcal P(Y)$ is at most \[ 2^k - \lfloor k/2\rfloor + 1, \] because compared to the maximal $2^k$ distinct images (one per subset), the $\lfloor k/2\rfloor$ colliding $A_i$'s force at least $\lfloor k/2\rfloor-1$ identifications. Since $2^k=n$ and $\lfloor k/2\rfloor\ge 1$ for $k\ge 2$, we have \[ 2^k - \lfloor k/2\rfloor + 1 < 2^k = n. \] Hence for this $Y$ we get $\#\{f(A):A\subseteq Y\}<n$, so $f$ cannot satisfy the defining property with $h=k$. Therefore $H(2^k)\ge k+1$.

(C) Why this does not yet imply $H(n)-\log_2 n\to\infty$.

The above shows only an additive $+1$ gap on the subsequence $n=2^k$. To prove $H(n)-\log_2 n\to\infty$ one would need to show that for each fixed constant $C$, and all sufficiently large $n$, no function $f$ can be surjective on $\mathcal P(Y)$ for every $Y$ of size $\lceil\log_2 n\rceil + C$. Equivalently, for such $h$, every $f$ must admit some $Y$ of size $h$ for which the range size $\#\{f(A):A\subseteq Y\}$ is $<n$.

A natural strengthening attempt is to produce, for some fixed output value, not merely $\Omega(n)$ colliding $2$-sets, but enough collisions inside a single $h$-set to reduce the range below $n$ even when $2^h$ is a constant multiple of $n$. However, when $h=\log_2 n + C$, we have $2^h = 2^C n$, so surjectivity is compatible with an average multiplicity $2^C$ of preimages per element, leaving room for many collisions without forcing a missing value. Forcing a missing value seems to require structure beyond a single pigeonhole collision at fixed set size.

VERIFICATION

The lower bound (A) is a direct counting argument. The proof in (B) uses only pigeonhole and the range-size bound $\#\mathrm{im}(f|_{\mathcal P(Y)})\le 2^{|Y|}$ together with a concrete collision count. The discussion in (C) correctly identifies that, for $h=\log_2 n + C$, collisions alone do not immediately prevent surjectivity because there is slack by the factor $2^C$.

FINAL

UNRESOLVED.

• (i) What was proved: The standard lower bound $H(n)\ge\log_2 n$ and (following Alon) the nontrivial step $H(2^k)\ge k+1$.
• (ii) Strongest partial result stated here: On the Erdős Problems page, Alon (personal communication) is reported to have a constant-factor deficit: for $n=2^k$ and any $f$, there exists $|Y|=k$ with $\#\{f(A):A\subseteq Y\}<(1-c)2^k$ for some absolute $c>0$ and large $k$.
• (iii) First gap: No argument here forces an unbounded additive gap $H(n)\ge \log_2 n + \omega(1)$; the collision method only yields an additive constant, and the presence of $2^C$ slack for $h=\log_2 n + C$ blocks a direct extension.
• (iv) Next concrete step: Develop a mechanism that, for any $f$, produces a set $Y$ of size $\log_2 n + o(\log_2 n)$ for which many values of $X$ are simultaneously missing from $\{f(A):A\subseteq Y\}$ (not just one), or else show that the distribution of $f$ on small subsets forces a structured obstruction (e.g. via entropy/compression, VC-dimension, or covering-design lower bounds) that grows with $n$.

COMPLETION ESTIMATE

COMPLETION: 25%.