Across all additive bases $A$ of $\mathbb{N}\setminus\{1\}$ of order $2$, what is the maximum possible value of the $n-$th term of $A?$

Question

Across all additive bases $A\subset \mathbb{N}$ of $\mathbb{N}\setminus\{1\}$ of order $2$, what is the maximum possible value of the $n-$th term of $A?$

For example, across all additive bases of $\mathbb{N}\setminus\{1\},$ the maximum possible value of the $1$st term of $A$ is $1,$ because $1$ must be the $1$st term, otherwise $2\not\in A+A,\implies A$ not an additive basis of $\mathbb{N}\setminus\{1\}$.

Across all additive bases of $\mathbb{N}\setminus\{1\},$ the maximum possible value of the $2$nd term of $A$ is $2$, because the first term of $A$ must be $1$ and if the $2$nd term of $A$ is not $2,$ then $3\not\in A+A.$

Across all additive bases of $\mathbb{N}\setminus\{1\},$ the maximum possible value of the $3$nd term of $A$ is $4$, because the first term of $A$ must be $1$ and the $2$nd term of $A$ must be $2,$ and if the third term of $A$ is $>4$ then $5\not\in A+A.$ But the third term can be $4,$ and so this is the maximum possible value the $3$rd term of $A$ can be.

Across all additive bases of $\mathbb{N}\setminus\{1\},$ the maximum possible value the $4$th term of $A$ can be is $6$, because the first term must be $1$ and the $2$nd term must be $2,$ and the best we can do is $\{1,2,3,6,\ldots\},\ $ or $\{1,2,4,6,\ldots\},\ $ either way the maximum possible value the $4$nd term of $A$ is $6$.

Across all additive bases of $\mathbb{N}\setminus\{1\},$ the maximum possible value of the $5$th term of $A$ is $10$, which can be achieved with, $\{1,2,4,5,10,\ldots\}.\ $ I don't think we can get $5$th term to be $11.$

This may also not necessarily have to do with the upper bounds of the growth rate of additive bases of $\mathbb{N}\setminus\{1\}$ themselves.

I wonder what the growth rate of the sequence of maximum possible numbers, $\{ 1,2,4,6,10,\ldots\},$ described in this question is. Maybe $n\log n?$ If so, why?

Answer 1

The sequence in this problem appears to be A234941. This is $2$ more than the corresponding term of A001212, the solution to the postage stamp problem. Let me try to explain the connection.

In this problem, the $n^{\text{th}}$ term $a_n$ is the maximum value such that we can find a set $A'$ of size $n-1$ such that $A' + A'$ contains $\{2, 3, \dots, a_n\}$. This is because:

• On one hand, if $a_n$ is the $n^{\text{th}}$ term of an additive basis $A$, then taking $A'$ to be the first $n-1$ terms of $A$ will satisfy this property.
• On the other hand, if $A'$ has this property, then $A' \cup \{a_n, a_n + 1, a_n + 2, \dots\}$ is an additive basis.

Rather than finding the set $A'$ such that $A' + A'$ contains $\{2,3, \dots, a_n\}$, it is equivalent to consider $B' = A' - 1$, and ask for $B'+B'$ to contain $\{0,1,\dots,a_n-2\}$. We must have $0 \in B'$. So if we exclude $0$ from $B'$, we have a set of size $n-2$ such that sums of one or two terms from $B'$ cover all of $\{1,2,\dots,a_n - 2\}$.

This is exactly the postage stamp problem with $n-2$ denominations of stamps, and at most $2$ stamps allowed per envelope; we are trying to maximize the value $x$ such that $1, 2, \dots, x$ are all representable by at most $2$ stamps, and by the correspondence above, $x$ will be exactly $a_n - 2$. This is why the entries of A001212 are always going to be exactly $2$ less than the solutions to this problem.

The OEIS sequence doesn't have any formulas, even asymptotic ones, but Mossige gives a construction showing that $a_n$ grows at least as fast as $\frac27 n^2$.