Erdős Problem #434

Erdős Problem #434: maximizing the number of nonrepresentable integers

Complete deduction from Dixmier's interval-count theorem, 24 September 2026.

1) Statement, including the singleton boundary

Among $k$-element sets $A\subseteq[1,n]$ with gcd one, which maximizes the number $H(A)$ of positive integers outside the semigroup generated by $A$? For $2\le k\le n$ we prove that the terminal interval $\{n-k+1,\ldots,n\}$ is a maximizer, without asserting uniqueness. For $k=1$, the only admissible set is $\{1\}$ and its count is zero; the proposed terminal singleton $\{n\}$ is not admissible unless $n=1$.

2) Bound every set by its interval deficits

The external input is Dixmier's theorem: if $|A|=k$, $\gcd(A)=1$, $m=\max A$ and $S=\langle A\rangle$, then \[|S\cap((j-1)m,jm]|\ge\min\{m,j(k-1)+1\}\qquad(j\ge1). \tag{1}\] All positive integers belong to exactly one of these blocks. Writing $h=k-1$, the total number missing is therefore at most \[H(A)\le\sum_{j\ge1}\max\{0,m-1-jh\}\le\sum_{j\ge1}\max\{0,n-1-jh\}=:\Psi_k(n). \tag{2}\] The sums are finite because their summands eventually vanish. The second inequality is termwise, so sets whose largest element is smaller than $n$ are included without an extra assumption.

3) The terminal interval attains the bound

Put $m=n-h$ and $A_*=\{m,m+1,\ldots,n\}$. Its gcd is one. Sums of exactly $j$ generators fill $[jm,jn]$: every offset in $[0,jh]$ is a sum of $j$ integers from $[0,h]$. The missing integers before the first such interval and between successive intervals consequently number \[\max\{0,jm-(j-1)n-1\}=\max\{0,n-1-jh\}\qquad(j\ge1). \] Once consecutive intervals overlap or touch, all subsequent ones do so as well, since this deficit decreases by $h$ at each step. Thus the displayed list accounts for every missing integer, and \[H(A_*)=\Psi_k(n). \] With $2$, this proves maximality.

There is also an exact formula. Write $n=qh+r$ with $1\le r\le h$, so $q=\lfloor(n-1)/h\rfloor$. Including a final zero summand when $r=1$, \begin{align*} \Psi_k(n)&=\sum_{j=1}^q(n-1-jh) =q(n-1)-\frac{h q(q+1)}2\\ &=\frac q2(n-k+r-1). \end{align*} The formula gives zero when $k=n$, as it should, and for $k=2$ it reduces to $(n-1)(n-2)/2$, the count for consecutive coprime generators $n-1,n$.

4) Outcome and attribution

SOLVED for $2\le k\le n$, with $k=1$ handled separately. The maximizing construction, exact count, and comparison for every gcd-one competitor follow from the declared interval theorem; its proof is not reproduced here. The largest missing integer and the number of missing integers are different extremal objectives, and no inference from one to the other was made.

Sources: https://www.erdosproblems.com/434, checked 24 September 2026, which attributes the extremal result to Kiss $2002$; J. Dixmier, https://doi.org/10.1016/0022-314X(90)90150-P; G. Kiss, The Frobenius exchange problem on competitions and in classroom, Problem 15, https://ojs.lib.unideb.hu/tmcs/article/download/14695/12597/33663, for the same interval count and its extremal context. No novelty or formal verification is claimed.

The estimate refers to the complete extremal deduction relative to $1$.

5) COMPLETION ESTIMATE

COMPLETION: 100%