Let
${\mathbb N}$
be the set of positive integers and put
${\mathbb N}_0={\mathbb N}\cup \{0\}$
. For
$n\in {\mathbb N}$
and given subsets
$\mathcal {A},\mathcal {M}$
of
${\mathbb N}$
, Canfield and Wilf [Reference Canfield and Wilf2] introduced the restricted integer partition function
$p(n,\mathcal {A},\mathcal {M})$
, defined as the number of representations of n in the form
$ n=\sum _{a\in \mathcal {A}}m_a a, $
where
$m_a\in \mathcal {M}\cup \{0\}$
for all
$a\in \mathcal {A}$
and only finitely many
$m_a$
are nonzero. The function
$p=p(n,\mathcal {A},\mathcal {M})$
is said to have polynomial growth if there exist a constant
$c>0$
and an integer
$n_0$
such that
$p(n,\mathcal {A},\mathcal {M})\le n^c$
for all
$n\ge n_0$
.
Answering a question of Canfield and Wilf [Reference Canfield and Wilf2] in a stronger form, Alon [Reference Alon1] proved that there are two explicit infinite sets
$\mathcal {A}$
and
$\mathcal {M}$
of positive integers such that
$p(n, \mathcal {A}, \mathcal {M})=1$
for all
$n\ge 1$
. For
$\mathcal {A}=\{n!\}_{n\ge 1}$
or for
$\mathcal {A}=\{n^n\}_{n\ge 1}$
, Alon further proved that there exist
$n_0$
and an infinite set
$\mathcal {M}$
of positive integers such that
for all
$n>n_0$
, thereby answering two further problems of Ljujić and Nathanson [Reference Ljujić and Nathanson4] in the affirmative. In 2016, via an elementary inductive argument, Dai and Chen [Reference Dai and Chen3] improved Alon’s exponent from
$8+o(1)$
to
$2+o(1)$
. More generally, Dai and Chen obtained a unified result for all subsets
$\mathcal {A}=\{1=a_1<a_2<\cdots \}$
satisfying
where
$c_2>c_1>0$
and
$\theta _2\ge \theta _1>0$
are constants. This led them to the following interesting question.
Question 1 (Dai and Chen, [Reference Dai and Chen3, Question 3.5]).
Do there exist two infinite sets
${\mathcal {A}=\{a_n\}_{n=1}^{\infty }}$
and
$\mathcal {M}$
of positive integers such that
$p(n,\mathcal {A},\mathcal {M})>0$
for all sufficiently large n and p has polynomial growth?
In this note, we show that the answer to Question 1 is affirmative. Before proving this corollary, we establish a more general result that relates additive complements to Question 1. Let
$\mathscr {B}$
and
$\mathscr {S}$
be subsets of
${\mathbb N}_0$
. We call
$\mathscr {B}$
and
$\mathscr {S}$
complete additive complements if every nonnegative integer can be represented as the sum of an element of
$\mathscr {B}$
and an element of
$\mathscr {S}$
, that is,
$\mathscr {B}+\mathscr {S}={\mathbb N}_0$
. For a set
$\mathcal {Y}\subseteq {\mathbb N}_0$
, let
$\mathcal {Y}(x)$
denote the number of elements of
$\mathcal {Y}$
not exceeding x. Our main result is stated as the following theorem.
Theorem 2. Let
$\mathscr {B}$
and
$\mathscr {S}$
be complete additive complements satisfying
Suppose that
Then,
$p(n, \mathcal {A}, \mathcal {M})>0$
for every
$n\in {\mathbb N}$
and p has polynomial growth.
Proof. By the hypothesis of the theorem, we have
We first show that
$p(n, \mathcal {A}, \mathcal {M})>0$
for every
$n\in {\mathbb N}$
. By the binary expansion of n, there is a finite nonempty set
$\mathcal {J}\subset {\mathbb N}_0$
such that
$ n=\sum _{j\in \mathcal {J}}2^j. $
By (1), each
$j\in \mathcal {J}$
can be written as
$j=s_j+b_j$
, where
$s_j\in \mathscr {S}$
and
$b_j\in \mathscr {B}$
. Thus,
Combining the terms in (2) with the same value of
$b_j$
,
For each fixed b, the corresponding
$s_j$
are distinct, because the j are distinct. Hence, each nonzero inner sum belongs to
$\mathcal {M}$
. Therefore,
$m_a\in \mathcal {M}\cup \{0\}$
for every
$a\in \mathcal {A}$
and only finitely many
$m_a$
are nonzero.
It remains to show that p has polynomial growth. Let n be sufficiently large and put
$N=\log n/\log 2$
. Take an arbitrary representation counted by
$p(n,\mathcal {A},\mathcal {M})$
as
For each b with
$m_{2^b}\ne 0$
, the uniqueness of the binary expansion gives a unique finite nonempty set
$\mathcal {D}_b\subset \mathscr {S}$
such that
Thus, the representation (3) determines a finite set
such that
Since all summands are positive, each pair in
$\mathcal {P}$
satisfies
$s+b\le N$
. Note that the map from representations to such sets
$\mathcal {P}$
is injective and so
where
By the hypothesis of our theorem,
where
$c_0>0$
is a constant. It follows from (4) that
completing the proof that p has polynomial growth.
Now, we turn back to Question 1. We shall use the following result of Ruzsa on additive complements of powers of two.
Proposition 3 (Ruzsa, [Reference Ruzsa5]).
There is a subset
$\mathcal {S}\subset \mathbb {N}$
with
$\mathcal {S}(x)\ll x/\log x$
such that every sufficiently large integer is of the form
$2^k+s$
, where
$k\in \mathbb {N}$
and
$s\in \mathcal {S}$
.
Corollary 4. The answer to Question 1 is affirmative.
Proof. Let
By Proposition 3, after adding finitely many nonnegative integers to
$\mathcal {S}$
if necessary, there exists some
$\mathcal {S}\subseteq {\mathbb N}_0$
such that
$\mathcal {S}(x)\ll x/\log x$
and
Indeed, finitely many missing values may be put into
$\mathcal {S}$
, since
$0\in \mathcal {B}$
, and this does not affect the estimate
$\mathcal {S}(x)\ll x/\log x$
. Since
$\mathcal {B}(x)\ll \log x$
for
$x\ge 2$
,
Let
where the elements of
$\mathcal {A}$
are listed in increasing order. Then,
$a_1=1$
and
$a_n=2^{2^{n-2}}$
for every
$n\ge 2$
. Hence,
Put
The set
$\mathcal {S}$
is infinite, otherwise
$\mathcal {B}+\mathcal {S}$
would have counting function
$O(\log x)$
and could not be all of
${\mathbb N}_0$
. Hence,
$\mathcal {M}$
is infinite. By Theorem 2,
$p(n, \mathcal {A}, \mathcal {M})>0$
for every
$n\in {\mathbb N}$
and p has polynomial growth, completing the proof of Corollary 4.
Acknowledgement
During the preparation of this work, the author used ChatGPT (OpenAI, GPT-5.5 Thinking) to explore possible approaches to Question 1. In particular, ChatGPT suggested considering sets of the form
$\mathcal {A}=2^{\mathcal {D}}$
and coefficients represented by binary subset sums, and pointed to a theorem of Ruzsa on additive complements of lacunary sequences. The author rewrote the proof and obtained a more general theorem.
Open access
