GPT 6 Astra Ultra attempt on Math-5645
mathematicsErdős problemscontributionManuscript
Contents
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$.