Erdős Problem #543

Erdős problem 543. Let $f(N)$ be the least $k$ such that, in every abelian group of order $N$, a uniformly chosen $k$-element subset spans the group by subset sums with probability at least $1/2$. Is $f(N)\leq\log_2N+o(\log\log N)$?

Status and attribution. No. The following reconstructs the rank-counting and moment argument of Quanyu Tang and ChatGPT-5.2 Pro, A note on problem #543, revised 23 January 2026: https://github.com/QuanyuTang/erdos-problem-543/blob/main/On_Erdos_Problem_543_Revised_and_Verified.pdf. The current problem page is https://www.erdosproblems.com/543, checked 24 September 2026. This is an exposition of that existing argument; the filename of the source is not a claim that this file has been formally verified.

Reduction to independent sampling. Let $p$ tend to infinity through primes, and let $k=\log_2p+o(\log\log p)$ be integral. Sample $a_1,\ldots,a_k$ independently and uniformly from $\mathbb F_p$. The probability of any repetition is at most $\binom k2/p=o(1)$. Conditional on no repetitions, the underlying set is a uniformly random $k$-subset. It therefore suffices to show that the indexed subset sums fail to cover $\mathbb F_p$ with probability tending to one.

Put $M=2^k-1$, $\lambda=M/p$, and $R=\lfloor(\log p)^{1/3}\rfloor$, with natural logarithms except where a base is displayed. Then \[ M=p^{1+o(1)},\qquad \lambda=(\log p)^{o(1)},\qquad \lambda=o(R),\qquad \lambda=o(\log p). \tag{1} \] For $B\subseteq\mathbb F_p$ with $m=|B|\in\{1,2\}$, let $X_B$ count pairs $(S,b)$ with $\varnothing\ne S\subseteq[k]$, $b\in B$, and $\sum_{i\in S}a_i=b$. We will prove uniformly over these target sets that \[ \mathbb P(X_B=0)=e^{-m\lambda}(1+o(1)). \tag{2} \]

Counting dependent patterns. For $r\leq R+1$, a list of distinct nonempty subsets $S_1,\ldots,S_r$ defines a binary incidence matrix $V$ of size $r$ by $k$. Let its rank be $d$. Its rational rank agrees with its rank modulo $p$ for all sufficiently large $p$: every nonzero minor has absolute determinant at most $r^{r/2}<p$, by Hadamard's bound. The equations $Va=b$ consequently have probability either zero or $p^{-d}$, according as $b$ lies outside or inside the image.

We need the following elementary cube bound. If the binary rows of $V$ are nonzero and distinct and $d<r$, its column space $W\subseteq\mathbb Q^r$ satisfies \[ |W\cap\{0,1\}^r|\leq(3/4)2^d. \tag{3} \] Choose $d$ coordinate positions giving an isomorphism $W\to\mathbb Q^d$. Each remaining coordinate is a homogeneous linear form in these $d$ coordinates. At least one such form has at least two nonzero coefficients: a zero form would force a zero row, and a form using just one coordinate would make two nonzero binary rows proportional, hence identical. For a form with two nonzero coefficients $a,b$, condition on its other inputs. The four equally likely values are $C,C+a,C+b,C+a+b$. They cannot all belong to $\{0,1\}$: if the first three do, nonzero $a,b$ must both be $1$ or both be $-1$, making the fourth leave that set. Thus at most three inputs work. This proves $3$.

There are at most $2^{rd}\leq2^{r^2}$ possible column spaces of rank $d$, since such a space has a basis of $d$ binary columns. Once the space is fixed, $3$ gives at most $((3/4)2^d)^k$ matrices. Therefore the number of ordered lists of distinct nonzero rows having rank $d<r$ is at most \[ 2^{r^2}(3/4)^k2^{dk}. \tag{4} \]

Uniform factorial moments. The factorial moment $\mathbb E(X_B)_r$ sums joint probabilities over ordered lists of distinct pairs $(S_i,b_i)$. If a subset repeats, its two targets must differ, so the equations are inconsistent. The number of these repeated-subset lists is at most $O(r^2m^rM^{r-1})$. For distinct subsets, every full-rank list contributes exactly $p^{-r}$. For deficient rank, $4$, with at most $m^r$ target assignments, bounds the total contribution by \[ m^r2^{r^2}(3/4)^k \sum_{d<r}(2^k/p)^d=p^{-\eta_0+o(1)},\qquad \eta_0=\log_2(4/3)>0. \tag{5} \] Here $r^2=o(\log p)$, and uniformly $d\leq R+1$, $d|\log(2^k/p)|=o(\log p)$. The same bound controls the full-rank baseline contribution erroneously assigned to these deficient lists, because $p^{-r}\leq p^{-d}$. The repeated-subset baseline is $O(r^2m^rM^{r-1}p^{-r})=p^{-1+o(1)}$. Finally \[ (mM)_r/p^r=(m\lambda)^r+O(p^{-1+o(1)}) \] uniformly, by the product expansion of the falling factorial and $r^2/M=o(1)$. Hence some absolute $\eta>0$ satisfies, uniformly for $1\leq r\leq R+1$ and all one- or two-point target sets, \[ \mathbb E(X_B)_r=(m\lambda)^r+O(p^{-\eta}). \tag{6} \]

From moments to missing targets. Bonferroni's inequalities bound $\mathbb P(X_B=0)$ between successive even and odd truncations of $\sum_r(-1)^r\mathbb E(X_B)_r/r!$. Using truncation orders $R$ and $R+1$, $6$ gives error $O(p^{-\eta})$, since $\sum1/r!\leq e$. The corresponding Taylor sums differ from $e^{-m\lambda}$ by at most $(m\lambda)^{R+1}/(R+1)!$ and its next-order analogue. These are $o(e^{-m\lambda})$: by $1$, their logarithms are at most $-(R+1)\log((R+1)/(em\lambda))$, whose magnitude dominates $\lambda$. Also $p^{-\eta}=o(e^{-m\lambda})$ because $\lambda=o(\log p)$. This proves $2$.

The second moment finishes the disproof. Let $U$ count the nonzero residues missed by all nonempty indexed subset sums. Formula $2$ gives \[ \mathbb EU=(p-1)e^{-\lambda}(1+o(1))\longrightarrow\infty, \] \[ \mathbb E[U(U-1)]=(p-1)(p-2)e^{-2\lambda}(1+o(1)). \] Thus $\operatorname{Var}U/(\mathbb EU)^2=o(1)$, and Chebyshev gives $\mathbb P(U=0)=o(1)$. Coverage includes every nonzero residue, so its probability is $o(1)$. Conditioning on the no-repetition event changes this limit by $o(1)$, establishing the same failure probability for a uniformly random $k$-subset.

Finally coverage probability is nondecreasing in the subset size, by sampling a random ordering and taking its successive initial sets. If the proposed upper bound for $f(p)$ held, enlarging to an integer $k=\log_2p+o(\log\log p)$ at least $f(p)$ would give coverage probability at least $1/2$, contradicting what was just proved.

Completion estimate. The prime-order counterexample, uniform missing-target estimate, and sampling conversion are all reconstructed above. COMPLETION: 100%

FORMAL RESTATEMENT. Let $N\ge 2$. Define $f(N)$ to be the minimal integer $k$ such that the following statement holds: for every finite abelian group $G$ with $|G|=N$, if $A\subseteq G$ is chosen uniformly at random among all $k$-element subsets of $G$, then \[ \Pr\left(\forall g\in G\ \exists S\subseteq A\text{ with } g=\sum_{x\in S} x\right)\ge \frac12. \] (Here the empty sum is $0\in G$.) The question asks whether \[ f(N) \le \log_2 N + o(\log\log N) \] as $N\to\infty$.

QUICK LITERATURE/CONTEXT CHECK. The problem statement reports an upper bound $f(N)\le \log_2 N+O(\log\log N)$ due to Erdős--Rényi, and also reports Erdős's belief that improving $O(\log\log N)$ to $o(\log\log N)$ should be impossible. Below I give self-contained lower bounds and analyze exactly the case $G\cong (\mathbb Z/2\mathbb Z)^d$.

ATTACK PLAN. 1) Prove basic counting lower bounds ($2^k\ge N$ is necessary). 2) Study explicit group families where subset-sums have clean algebraic meaning (notably exponent-2 groups). 3) Compute exact small-$N$ probabilities to sanity-check the scale.

WORK. Fast reality check (exact small-$N$ probabilities). For cyclic groups $G=\mathbb Z/N\mathbb Z$ with $N\le 12$, I enumerated all $k$-subsets and computed the exact probability that subset sums cover $G$. The minimal $k$ with probability $\ge 1/2$ was: \[ \begin{array}{c|ccccccccccc} N &2&3&4&5&6&7&8&9&10&11&12\\\hline \min k &1&3&3&4&4&4&4&5&5&5&5 \end{array} \] For elementary $2$-groups $G\cong (\mathbb Z/2\mathbb Z)^d$ (size $N=2^d$), exact enumeration for $d\le 4$ gave: \[ \begin{array}{c|cccc} d &1&2&3&4\\\hline N=2^d &2&4&8&16\\\hline \min k &1&2&3&5 \end{array} \]

Lemma 543.1 (counting lower bound). For every $N\ge 2$, \[ f(N)\ge \lceil\log_2 N\rceil. \]

Proof. Fix $G$ with $|G|=N$ and any subset $A\subseteq G$ of size $k$. The set of all subset sums of $A$ has cardinality at most $2^k$ because there are $2^k$ subsets $S\subseteq A$. If all elements of $G$ are representable as subset sums, then $N\le 2^k$. Therefore a necessary condition for the coverage property to hold (for any $G$ and any $A$) is $2^k\ge N$, i.e. $k\ge \lceil\log_2 N\rceil$. Since $f(N)$ is defined as a minimal such $k$, it must satisfy this bound. $\square$

Proposition 543.2 (exact threshold for $G=(\mathbb Z/2\mathbb Z)^d$ up to $\pm1$). Let $G=(\mathbb Z/2\mathbb Z)^d$ with $N=2^d$. A $k$-subset $A\subseteq G$ has the property that every element of $G$ is a subset sum of $A$ if and only if $A$ spans $G$ as an $\mathbb F_2$-vector space. Moreover:

• If $k=d$, then \[ \Pr(A\text{ spans }G)=\prod_{j=0}^{d-1}\frac{2^d-2^j}{2^d-j}. \] In particular, for $d\ge 4$ this probability is $<1/2$.
• If $k=d+1$ and $d\ge 3$, then $\Pr(A\text{ spans }G)>1/2$.

Proof. Step 1: subset sums = linear span. In $G=(\mathbb Z/2\mathbb Z)^d$, every element has order $2$, so adding an element twice gives $0$. Given $A\subseteq G$, any subset sum $\sum_{x\in S} x$ is exactly an $\mathbb F_2$-linear combination of the elements of $A$ with coefficients in $\{0,1\}$. Conversely, every $\mathbb F_2$-linear combination uses each vector with coefficient $0$ or $1$, hence is a subset sum. Therefore the set of subset sums is exactly the $\mathbb F_2$-span of $A$. Thus it equals all of $G$ if and only if $A$ spans.

Step 2: formula for spanning probability when $k=d$. Choose $A$ uniformly among $d$-element subsets. Expose the elements sequentially: after choosing $j$ linearly independent vectors, their span has size $2^j$. At the next selection step, there are $2^d-j$ remaining vectors not yet chosen. Among these, exactly $2^j-j$ lie in the current span but are not already chosen. Hence the number of remaining vectors outside the span is $(2^d-j)-(2^j-j)=2^d-2^j$, and the conditional probability that the next chosen vector increases the rank is $(2^d-2^j)/(2^d-j)$. Multiplying these conditional probabilities for $j=0,1,\dots,d-1$ yields \[ \Pr(A\text{ is a basis})=\prod_{j=0}^{d-1}\frac{2^d-2^j}{2^d-j}. \] For $d=4$ this equals $ \frac{15}{16}\cdot\frac{14}{15}\cdot\frac{12}{14}\cdot\frac{8}{13}=\frac{6}{13}<\frac12. $ Now assume $d\ge 5$. For each $j\in\{0,1,\dots,d-1\}$ we have $2^j>j$ (indeed $2^j\ge j+1$ for all $j\ge 0$), hence $2^d-2^j < 2^d-j$ and so every factor $(2^d-2^j)/(2^d-j)$ is $<1$. Therefore the full product is bounded by the product of its last three factors: \[ \Pr(A\text{ spans}) \le \prod_{j=d-3}^{d-1}\frac{2^d-2^j}{2^d-j}. \] Writing these three factors explicitly, \[ \prod_{j=d-3}^{d-1}\frac{2^d-2^j}{2^d-j} =\frac{2^d-2^{d-3}}{2^d-(d-3)}\cdot\frac{2^d-2^{d-2}}{2^d-(d-2)}\cdot\frac{2^d-2^{d-1}}{2^d-(d-1)}. \] Factor out $2^d$ from each ratio to get \[ =\frac{7/8}{1-(d-3)/2^d}\cdot\frac{3/4}{1-(d-2)/2^d}\cdot\frac{1/2}{1-(d-1)/2^d}. \] For $d\ge 5$ one has $(d-1)/2^d\le 4/32=1/8$, so each denominator term is at least $1-1/8=7/8$. Hence \[ \Pr(A\text{ spans}) \le \frac{21}{64}\cdot\frac{1}{(7/8)^3}=\frac{168}{343}<\frac12. \] Combining with the explicit $d=4$ computation, we conclude that for all $d\ge 4$, with $k=d$ the success probability is $<1/2$.

Step 3: $k=d+1$ succeeds with probability $>1/2$ for $d\ge 3$. Failure to span means $A$ is contained in some proper subspace. Every proper subspace is contained in a codimension-$1$ subspace (a hyperplane). In $G=(\mathbb Z/2\mathbb Z)^d$, the number of distinct hyperplanes equals the number of nonzero linear functionals, which is $2^d-1$. Fix a hyperplane $H$; it has size $2^{d-1}$. The probability that a uniformly random $(d+1)$-subset $A$ lies entirely inside this fixed $H$ is $ \binom{2^{d-1}}{d+1}/\binom{2^d}{d+1}. $ Using the product formula for binomial ratios, \[ \frac{\binom{2^{d-1}}{d+1}}{\binom{2^d}{d+1}}= \prod_{i=0}^{d}\frac{2^{d-1}-i}{2^d-i}. \] For each $i\ge 0$, $ \frac{2^{d-1}-i}{2^d-i}\le \frac{1}{2} $ because $2(2^{d-1}-i)=2^d-2i\le 2^d-i$. Therefore \[ \frac{\binom{2^{d-1}}{d+1}}{\binom{2^d}{d+1}}\le 2^{-(d+1)}. \] By the union bound over all $2^d-1$ hyperplanes, \[ \Pr(A\text{ fails to span}) \le (2^d-1)\cdot 2^{-(d+1)}< 2^d\cdot 2^{-(d+1)}=\frac12. \] So $\Pr(A\text{ spans})>1/2$ for $d\ge 3$.

Step 4: implication for $f(2^d)$. For $d\ge 4$, we have shown that in this specific group, $k=d$ gives success probability $<1/2$. Hence any $k$ that works in the definition of $f(2^d)$ must be at least $d+1$. Thus $f(2^d)\ge d+1=\log_2(2^d)+1$. $\square$

VERIFICATION. The key coupling in Proposition 543.2 is valid because in exponent-$2$ groups, subset sums coincide with $\mathbb F_2$-linear combinations. In Step 3, the only estimate used is that a random $(d+1)$-subset lying in a fixed half-size hyperplane has probability at most $2^{-(d+1)}$, proved term-by-term.

FINAL.\;UNRESOLVED.

• (i) Strongest proved partial result. Always $f(N)\ge \lceil\log_2 N\rceil$ (Lemma 543.1). Moreover, for $N=2^d$ with $d\ge 4$, considering $G\cong(\mathbb Z/2\mathbb Z)^d$ yields the stronger lower bound $f(2^d)\ge d+1=\log_2 N+1$ (Proposition 543.2).
• (ii) First gap (crisp statement). Decide whether there exists a sequence of group orders $N\to\infty$ for which $f(N)\ge \log_2 N + c\log\log N$ (for some absolute $c>0$), which would refute $\log_2 N+o(\log\log N)$; or conversely, prove $f(N)\le \log_2 N+o(\log\log N)$ uniformly over all abelian $|G|=N$.
• (iii) Top 3 next moves.
  • Analyze cyclic groups $\mathbb Z/N\mathbb Z$ (or groups with large odd-order components) using Fourier methods for the random subset-sum walk to estimate the expected number of uncovered elements as a function of $k$.
  • Seek worst-case groups: understand which abelian group structures maximize the probability that a random $k$-subset has many collisions among its subset sums.
  • Computationally: for moderate $N$ (say $N\le 200$), Monte Carlo estimate the coverage probability in different group types to guess the extremal family.
• (iv) Minimal counterexample structure to look for. To force $f(N)\ge \log_2 N + \omega(1)$, one needs an abelian group in which random subset sums exhibit many collisions so that the multiset of $2^k$ sums fails to cover $G$ even when $2^k$ is moderately larger than $N$; cyclic groups (or groups with large odd exponent) are natural candidates because the subset-sum map is not an $\mathbb F_2$-linear map there.