%~Mouliné par MaN_auto v.0.29.1 2023-11-17 14:29:11
\documentclass[CRMATH, Unicode, XML,published]{cedram}

\TopicFR{Théorie des nombres}
\TopicEN{Number theory}

\usepackage{amssymb}

\makeatletter
\def\@setafterauthor{%
  \vglue3mm%
%  \hspace*{0pt}%
\begingroup\hsize=12cm\advance\hsize\abstractmarginL\raggedright
\noindent
%\hspace*{\abstractmarginL}\begin{minipage}[t]{10cm}
   \leftskip\abstractmarginL
  \normalfont\Small
  \@afterauthor\par
\endgroup
\vskip2pt plus 3pt minus 1pt
}
\makeatother

\newtheorem{theol}{Theorem}
\renewcommand*\thetheol{\Alph{theol}}

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\relabel}{\renewcommand{\labelenumi}{(\theenumi)}}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}\relabel}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}\relabel}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}\relabel}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}\relabel}


\title{On a problem of Nathanson related to minimal asymptotic bases of order $h$}

\author{\firstname{Shi-Qiang} \lastname{Chen}}
\address{School of Mathematics and Statistics, Anhui Normal University, Wuhu 241002, P. R. China}
\email{csq20180327@163.com}

\author{\firstname{Csaba} \lastname{S\'andor}}
%\address{Department of Stochastics, Institute of Mathematics and Department of Computer Science and Information Theory, Budapest University of Technology and Economics, M\H{u}egyetem rkp. 3., H-1111 Budapest, Hungary}
\address{Department of Stochastics, Institute of Mathematics, BudapestUniversity of Technology and Economics, M\H{u}egyetem rkp. 3., H-1111 Budapest, Hungary}
\address{Department of Computer Science and Information Theory, Budapest University of Technology and Economics, M\H{u}egyetem rkp. 3., H-1111 Budapest, Hungary}
\address{MTA-BME Lendület Arithmetic Combinatorics Research Group, ELKH, M\H{u}egyetem rkp. 3., H-1111 Budapest, Hungary}
\email{csandor@math.bme.hu}

\author{\firstname{Quan-Hui} \lastname{Yang}\IsCorresp}
\address{School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing 210044, China}
\email{yangquanhui01@163.com}

\thanks{S.Q.Chen is supported by the National Natural Science Foundation of China, Grant No.~12301003, the Anhui Provincial Natural Science Foundation (Grant No.~2308085QA02) and the University Natural Science Research Project of Anhui Province (Grant No.~2022AH050171).
C.S. was supported by the NKFIH Grants No.~K129335.
Q.H.Yang is supported by the National Natural Science Foundation of China, Grant No.~12371005.}
\CDRGrant[National Natural Science Foundation of China]{12301003}
\CDRGrant[Anhui Provincial Natural Science Foundation]{2308085QA02}
\CDRGrant[University Natural Science Research Project of Anhui Province]{2022AH050171}
\CDRGrant[NKFIH]{K129335}
\CDRGrant[National Natural Science Foundation of China]{12371005}

\begin{abstract}
For integer $h\geq2$ and $A\subseteq\mathbb{N}$, we define $hA$ to be the set of all integers which can be written as a sum of $h$, not necessarily distinct, elements of $A$. The set $A$ is called an asymptotic basis of order $h$ if $n\in hA$ for all sufficiently large integers $n$. An asymptotic basis $A$ of order $h$ is minimal if no proper subset of $A$ is an asymptotic basis of order $h$. For $W\subseteq\mathbb{N}$, denote by $\mathcal{F}^*(W)$ the set of all finite, nonempty subsets of $W$. Let $A(W)$ be the set of all numbers of the form $\sum_{f \in F} 2^f$, where $F \in \mathcal{F}^*(W)$. In this paper, we give some characterizations of the partitions $\mathbb{N}=W_1\cup\dots \cup W_h$ with the property that $A=A(W_1)\cup\dots \cup A(W_{h})$ is a minimal asymptotic basis of order $h$. This generalizes a result of Chen and Chen, recent result of Ling and Tang, and also recent result of Sun.
\end{abstract}

\subjclass{11B34}
\keywords{\kwd{Asymptotic bases}
\kwd{minimal asymptotic bases}
\kwd{binary representation}}

\dateposted{2024-02-02}
\begin{document}
\maketitle

\section{Introduction}

Let $\mathbb{N}$ be the set of all nonnegative integers. For an integer $h\geq2$ and $A\subseteq\mathbb{N}$, we define
\[
hA = \{n: n= a_1+\dots+a_h, a_i\in A, i = 1, 2,\dots,h\}.
\]
The set $A$ is called an asymptotic basis of order $h$ if $n\in hA$ for all sufficiently large integers $n$. An asymptotic basis $A$ of order $h$ is minimal if no proper subset of $A$ is an asymptotic basis of order $h$. This means that for any $a\in A$, the set $E_a = hA\setminus h(A\setminus\{a\})$ is infinite.

Let $W$ be a nonempty subset of $\mathbb{N}$. Denote by $\mathcal{F}^{*}(W)$ the set of all finite, nonempty subsets of $W$. Let $A(W)$ be the set of all numbers of the form $\sum_{f\in F}2^f$, where $F\in \mathcal{F}^{*}(W)$.

In 1988, Nathanson~\cite{N1988} gave a construction of minimal asymptotic bases of order $h$.

\begin{theol}\label{thA}
Let $h\geq2$ and let $W_i=\{n\in\mathbb{N}:n\equiv i\pmod {h}\}$ for $i=0, 1,\dots, h-1$. Let
$A = A(W_0)\cup A(W_1)\cup\dots\cup A(W_{h-1})$. Then $A$ is a minimal asymptotic basis of order $h$.
\end{theol}

Let $h\geq2$ and $\mathbb{N}=W_1\cup\dots \cup W_h$ be a partition; that is, $W_i\cap W_j=\emptyset$ if $i\neq j$. Nathanson also posed the following open problem:

\begin{enonce}{Problem}\label{pro1}
Characterise the partitions $\mathbb{N}=W_1\cup\dots \cup W_h$ with the property that
$A=A(W_1)\cup\dots \cup A(W_{h})$ is a minimal asymptotic basis of order $h$.
\end{enonce}

In 2011, Chen and Chen~\cite{CC2011} solved Problem~\ref{pro1} for $h=2$. They proved the next theorem.

\begin{theol}\label{thB}
Let $\mathbb{N}=W_1\cup W_2$ be a partition with $0\in W_1$ such that $W_1$ and $W_2$ are infinite. Then $A=A(W_1)\cup A(W_2)$ is a minimal asymptotic basis of order $2$ if and only if either $W_1$ contains no consecutive integers or $W_2$ contains consecutive integers or both.
\end{theol}

In 2020, Ling and Tang~\cite{LT2020} focus on Problem~\ref{pro1} for $h=3$; they proved the following result:

\begin{theol}\label{thC}
For any $i\in\{0,1,2,3,4,5\}$, if $W_0=\{n\in\mathbb{N}:n\equiv i,i+1\pmod{6}\}$, $W_1=\{n\in\mathbb{N}:n\equiv i+2,i+4\pmod{6}\}$ and $W_2=\{n\in\mathbb{N}:n\equiv i+3,i+5\pmod{6}\}$, then $A=A(W_0)\cup A(W_1) \cup A(W_{2})$ is a minimal asymptotic basis of order three.
\end{theol}

In 2021, Sun~\cite{S2021} gave a generalization of Theorem~\ref{thA}.

\begin{theol}\label{thD}
Let $h$ and $t$ be two positive integers with $h\geq2$. Let
\[
W_j=\bigcup_{i=0}^{\infty}[iht+jt,iht+jt+t-1]
\]
for $j=0,1,\dots,h-1$. Then $A = A(W_0)\cup A(W_1)\cup\dots\cup A(W_{h-1})$ is a minimal asymptotic basis of order~$h$.
\end{theol}

In 2011, Chen and Chen~\cite{CC2011} gave the following sufficient condition for Problem~\ref{pro1}.

\begin{theol}\label{thE}
Let $h\ge 2$ and $r$ be the least integer with $r>\log h/\log 2$. Let $\mathbb{N}=W_1\cup \dots \cup W_h$ be a partition such that each set $W_i$ is infinite and contains $r$ consecutive integers for $i=1,\dots,h$. Then $A=A(W_1)\cup \dots \cup A(W_h)$ is a minimal asymptotic basis of order $h$.
\end{theol}

For other related results about minimal asymptotic bases, see~\cite{CT2018, E1980, E1956, T2010, S1955, T2022}.%[2-5,10,11].

In this paper, we continue to focus on Problem~\ref{pro1}. First, we give a generalization of Theorem~\ref{thC} and Theorem~\ref{thD}. For $W\subseteq \mathbb{N}$, set $W(x)=|\{n\in W:n\leq x\}|$.

\begin{theo}\label{thm1}
Let $h\geq2$ be an integer and $\mathbb{N}=W_1\cup\dots \cup W_h$ be a partition such that each set $W_j~(1\le j\le h)$ satisfies $|W_j(ht-1)|=t$ for infinitely many integers $t$. Then $A=A(W_1)\cup\dots \cup A(W_h)$ is a minimal asymptotic basis of order $h$.
\end{theo}

Our second theorem is a generalization of Theorem~\ref{thE}.

\begin{theo}\label{thm2}
Let $h$ be an integer, $h\ge 2$, and $\mathbb{N}=W_1\cup \dots \cup W_h$ be a partition such that each set $W_i$ is infinite for $i=1,\dots,h$, $0\in W_1$ and every $W_i$ contains $\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil $ consecutive integers for $i=2,\dots,h$. Then $A=A(W_1)\cup \dots \cup A(W_h)$ is a minimal asymptotic basis of order $h$.
\end{theo}

\begin{rema}
It is easy to see that $\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil $ is the least integer greater than $\log h/\log 2$.
\end{rema}

There is a more limited variant of Problem~\ref{pro1}, see~\cite{JN1989, N1989, T2022}
%[6,9,12].

\section{Lemmas}

\begin{lemm}[{see~\cite[Lemma~1]{N1988}}]\label{lem1}
Let $\mathbb{N}=W_1\cup\dots \cup W_h$, where $W_i\neq \emptyset$ for $i=1,\dots,h$. Then $A=A(W_1)\cup\dots \cup A(W_h)$ is an asymptotic basis of order $h$.
\end{lemm}

\begin{lemm}\label{lem2}
Let $w_1,\dots,w_s$ be $s$ distinct nonnegative integers. If
\[
\sum_{i=1}^{s}2^{w_i}\equiv\sum_{j=1}^{t}2^{x_j}\pmod{2^{w_s+1}},
\]
where $0\leq x_1,\dots, x_t<w_s+1$ are integers not necessarily distinct, then there exist nonempty disjoint sets $J_1,\dots,J_s$ of $\{1,2,\dots,t\}$ such that
\[
2^{w_i}=\sum_{j\in J_i}2^{x_j}
\]
for $i=1,\dots,s$.
\end{lemm}

\begin{proof}
By the proof of Lemma~2 from~\cite{N1988}, there exist nonempty subsets $J_1,\dots,J_s$ of $\{1,2,\dots,t\}$ such that
\[
2^{w_i}=\sum_{j\in J_i}2^{x_j}
\]
for $i=1,\dots,s$.

The result is trivial for $s=1$. Now we assume that $s\geq 2$. Since there exists a subset $J_1$ of $\{1,2,\dots,t\}$ such that
\[
2^{w_1}=\sum_{j\in J_1}2^{x_j},
\]
it follows that
\[
\sum_{2\leq i\leq s}2^{w_i}\equiv\sum_{j\in\{1,\dots,t\}\setminus J_1}2^{x_j}\pmod{2^{w_s+1}},
\]
which implies that there exists a subset $J_2$ of $\{1,2,\dots,t\}\setminus J_1$ such that
\[
2^{w_2}=\sum_{j\in J_2}2^{x_j},
\]
and so $J_1\cap J_2=\emptyset$. Continuing this process, it follows that there exist nonempty disjoint subsets $J_1,\dots,J_s$ of $\{1,2,\dots,t\}$ such that
\[
2^{w_i}=\sum_{j\in J_i}2^{x_j},
\]
for $i=1,\dots,s$.

This completes the proof of Lemma~\ref{lem2}.
\end{proof}


\section{Proof of Theorem~\ref{thm1}}

By Lemma~\ref{lem1}, it follows that $A$ is an asymptotic basis of order $h$. For any $a\in A$, there exists $j\in\{1,2,\dots,h\}$ such that $a\in A(W_j)$. Without loss of generality, we may assume that $a\in A(W_1)$. Then there exists a set $K\subseteq W_1$ such that $a=\sum_{i\in K}2^{i}$.
Since there exist infinitely many $t$ such that
\[
|W_j(ht-1)|=t
\]
for $j=1,2,\dots,h$, it follows that there exists an integer $t_{n}$ such that
\[
t_{n}h\leq \min K<t_{n+1}h.
\]
Let
\[
n_T=a+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[t_{n+1}h,T]}2^v,
\]
where $T$ is an integer such that $2^T>a$. Next we shall prove that $n_T\in E_a$. Note that $K(t_{n+1}h-1)\neq\emptyset$ and
\[
n_T=\sum_{j\in K(t_{n+1}h-1)}2^{j}+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v+2^{t_{n+1}h}m
\]
for some $m\geq0$. Let $n_T=b_1+b_2+\dots+b_h$ be any representation of $n_T$ as a sum of $h$ elements of $A$ and let
\[
b_i=\sum_{i\in S_i}2^{i}
\]
for $i=1,2\dots,h$.
Let
\[
c_i=\sum_{j\in S_i(t_{n+1}h-1)}2^{j}
\]
for $i=1,2,\dots,h$. Then
\[
c_i\equiv b_i\pmod{2^{t_{n+1}h}}
\]
and
\[
|S_i(t_{n+1}h-1)|\leq t_{n+1}
\]
for $i=1,2,\dots,h$, which implies that
\[
\sum_{k\in K(t_{n+1}h-1)}2^{k}+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v\equiv \sum_{1\leq i\leq h}c_i\equiv\sum_{1\leq i\leq h}\:\sum_{j\in S_i(t_{n+1}h-1)}2^{j}\pmod{2^{t_{n+1}h}}.
\]
Let
\[
\sum_{k\in K(t_{n+1}h-1)}2^{k}+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v\equiv\sum_{j=1}^{s}2^{x_j}\pmod{2^{t_{n+1}h}},
\]
where $s$ is an integer such that $s\leq t_{n+1}h$. By Lemma~\ref{lem2}, there exist nonempty disjoint subsets $J_0,J_1,\dots,J_{t_{n+1}(h-1)}$ of $\{1,2,\dots,s\}$ such that
\[
2^{\min K}+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v=\sum_{j\in J_0}2^{x_j}+\sum_{j\in J_1}2^{x_j}+\sum_{j\in J_2}2^{x_j}+\dots+\sum_{j\in J_{t_{n+1}(h-1)}}2^{x_j}.
\]
Therefore,
\[
1+t_{n+1}(h-1)\leq1+|J_1|+\dots+|J_{t_{n+1}(h-1)}|\leq s\leq t_{n+1}h,
\]
and so
\begin{equation}\label{equation1}
t_{n+1}(h-1)\leq|J_1|+\dots+|J_{t_{n+1}(h-1)}|\leq t_{n+1}h-1.
\end{equation}
Since $|W_j(t_{n+1}h-1)|=t_{n+1}$ for any $j\geq2$, it follows from~\eqref{equation1} and Lemma~\ref{lem2} that for any $j\geq 2$, there exist $w\in W_j$, $J\subseteq \{1,2,\dots,s\}$ and $|J|=1$ such that
\[
2^w=\sum_{j\in J}2^{x_j},
\]
which implies that $x_j=w\in W_j$,
and so
\[
\{b_1,\dots,b_h\}\not\subseteq\bigcup_{j=1,j\neq m}^{h}A(W_j)
\]
for any $m\geq 2$.
Renumbering the indexes, we always assume that
\[
b_i\in A(W_i),\quad i\geq2.
\]
Then
\[
b_1=a+\left(\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[0,t_{n+1}h-1]}2^v+\sum_{j=2}^{h}\:\sum_{v\in W_j\cap[t_{n+1}h,T]}2^v-\sum_{2\leq i\leq h}b_i\right).
\]
Since the binary representation of $b_1$ is unique, it follows that $b_1=a$, that is $n_T\in E_a$. Noting that $T$ is infinite, we have that $A$ is minimal.

This completes the proof of Theorem~\ref{thm1}.


\section{Proof of Theorem~\ref{thm2}}

By Lemma~\ref{lem1}, it follows that $A$ is an asymptotic basis of order $h$. For $a\in A$, we assume that $a\in A(W_i)$. Let $E_a=hA\setminus h(A\setminus \{ a\})$. Now we prove that $E_a$ is infinite.

Let
\[
n_T=a+\sum_{w\in [0,T]\setminus W_i}2^w,
\]
where $T$ is an integer with $T>a$ such that each $[0,T]\cap W_j$ contains $\big\lceil \frac{\log (h+1)}{\log 2}\big\rceil $ consecutive integers for $j=2,\dots,h$. To prove that $n_T\in E_a$, it suffices to prove that if $n_T=a_1+a_2+\dots +a_h$ with $a_i\in A$ for $1\le i\le h$, then there exists at least one $a_k=a$.

We distinguish two cases according to whether $i=1$ or $2\le i\le h$.

\begin{proof}[Case 1. $i=1$]
Suppose that there exists an integer $j\ge 2$ such that
\[
\{ a_1,a_2,\dots,a_h\} \subseteq \bigcup_{1\le l\le h, l\ne j}A(W_j).
\]
Let $\bigl\{ b+1,b+2,\dots,b+\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil \bigr\}\subseteq [0,T]\cap W_j$. Then by Lemma~\ref{lem2} there exists
\[
\{ a_1',\dots,a_h'\} \subseteq \bigcup_{1\le l\le h, l\ne j}A(W_j)\cup \{0\}
\]
such that
\[
2^{b+1}+\dots +2^{b+\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil}=a_1'+\dots +a_h'.
\]
Since $a_i'\notin A(W_j)$ for $i=1, \dots,h$, we have
\[
a_i'\le 2^0+2^1+\dots +2^b=2^{b+1}-1
\]
for $i=1,\dots,h$. It follows that
\[
2^{b+1}+\dots +2^{b+\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil}\le h(2^{b+1}-1)<h2^{b+1},
\]
that is $2^{\bigl\lceil \frac{\log (h+1)}{\log 2}\bigr\rceil}-1<h$, a contradiction. Hence, for any integer $j\ge 2$, we have
\[
\{ a_1,a_2,\dots,a_h\} \nsubseteq \bigcup_{1\le l\le h, l\ne j}A(W_l).
\]
Renumbering the indexes, we may assume that $a_i\in A(W_i)$ for $i=2,3,\dots,h$. It follows that
\[
a_1=a+\sum_{2\le j\le h}\left(\sum_{w\in [0,T]\cap W_j}2^w-a_j\right).
\]
Since $a\in A(W_1)$, $W_1,\dots,W_h$ are disjoint, and the binary representation of $a_1$ is unique, we have $a_1=a$. Therefore $n_T\in E_a$, and $E_a$ is infinite.
\let\qed\relax
\end{proof}

\begin{proof}[Case 2. $i\ge 2$]
Since $n_T$ is odd, therefore we may assume that $a_1\in A(W_1)$. Let $2\le j\le h$, $j\ne i$. Similar to the Case 1, we get that
\[
\{ a_1,\dots,a_h\} \nsubseteq \bigcup_{1\le k\le h, k\ne j}A(W_k).
\]
Renumbering the indexes, we may assume that $a_j\in A(W_j)$ for $j=2,3,\dots,i-1,i+1,\dots,h$. It follows that
\[
a_i=a+\sum_{1\le j\le h, j\ne i}\left(\sum_{w\in [0,T]\cap W_j}2^w-a_j\right).
\]
Since $a\in A(W_i)$, $W_1,\dots,W_h$ are disjoint, and the binary representation of $a_i$ is unique, we have $a_i=a$. Therefore $n_T\in E_a$, and $E_a$ is infinite.

This completes the proof.
\let\qed\relax
\end{proof}

\subsection*{Acknowledgements}

We would like to thank the anonymous reviewer for the valuable and detailed comments, which helps us to improve the manuscript.

\bibliographystyle{crplain}
\bibliography{CRMATH_Yang_20230174}
\end{document}