\documentclass[12pt,a4paper]{article} %\textheight42pc %\textwidth27pc \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage[francais]{babel} \usepackage{amsmath} \usepackage{amssymb} %\setlength{\topmargin}{-0.5cm} %\setlength{\textheight}{22.5cm} %\setlength{\footskip}{2.7cm} %\setcounter{equation}{267} %\renewcommand{\theequation}{\thesection.\arabic{equation}} \numberwithin{equation}{section} \newcommand{\R}{\mbox{$\mathbb{R}$}} \newcommand{\K}{\mbox{$\mathbb{K}$}} \newcommand{\C}{\mbox{$\mathbb{C}$}} \newcommand{\N}{\mbox{$\mathbb{N}$}} \newcommand{\nb}{\mbox{$\mathbb{N}$}} \newcommand{\Z}{\mbox{$\mathbb{Z}$}} \newcommand{\zb}{\mbox{$\mathbb{Z}$}} \newcommand{\Q}{\mbox{$\mathbb{Q}$}} \newcommand{\F}{\mbox{$\mathbb{F}$}} \def\ds{\displaystyle} \def\inf{\infty} \def\be{\beta} \def\al{\alpha} \def\ga{\gamma} \def\Ga{\Gamma} \def\de{\delta} \def\De{\Delta} \def\la{\lambda} \def\te{\theta} \def\vep{\varepsilon} \def\vfi{\varphi} \def\om{\omega} \def\Om{\Omega} \def\si{\sigma} \def\ca{\mathcal{A}} \def\cb{\mathcal{B}} \def\cf{\mathcal{F}} \def\cn{\mathcal{N}} \def\cg{\mathcal{G}} \def\cp{\mathcal{P}} \def\cc{\mathcal{C}} \def\cd{\mathcal{D}} \def\aca{\mathcal{|A|}} \def\acb{\mathcal{|B|}} \def\sark{S\'ark\"ozy } \def\ni{\noindent} \def \dv{\,|\,} \def\lcm{\textrm{lcm}} \newcommand{\leg}[2]{\left(\frac{#1}{#2}\right)} \begin{document} \phantom{.} \vskip 1 true cm \centerline{\bf EVEN PARTITION FUNCTIONS} \bigskip \centerline{\bf by} \bigskip \centerline {\bf F. Ben sa\"{\i}d\footnote{Research partially supported by French-Tunisian exchange program, C.M.C.U. $n^o$ 99/F 1507 and by CNRS, Institut Girard Desargues, UMR 5028.}} \centerline {Facult\'e des Sciences de Monastir} \centerline {Avenue de l'environnement} \centerline {5000, Monastir, Tunisie} \centerline {e-mail : {\tt Fethi.BenSaid@fsm.rnu.tn}} \medskip \centerline{and} \medskip \centerline{\bf J.-L. Nicolas\footnotemark[1]} \centerline{Institut Girard Desargues, UMR 5028,} \centerline{B\^at. Doyen Jean Braconnier,} \centerline{Universit\'e Claude Bernard (Lyon 1),} \centerline{21 Avenue Claude Bernard,} \centerline{F-69622 Villeurbanne Cedex, France} \centerline{e-mail: {\tt jlnicola@in2p3.fr}} %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\accent19eminaire Lotharingien de Combinatoire \bfs 46 \rms (2002), Article~B46i\hfill} \def\thepage{} \vskip 1 true cm \ni {\bf Abstract.} Let ${\cal A}$ be a set of positive integers. Let us denote by $p({\cal A}, n)$ the number of partitions of $n$ with parts in ${\cal A}$. While the study of the parity of the classical partition function $p(\N,n)$ (where $\N$ is the set of positive integers) is a deep and difficult problem, it is easy to construct a set ${\cal A}$ for which $p({\cal A},n)$ is even for $n$ large enough : as explained in a paper of I.Z. Ruzsa, A. \sark and J.-L. Nicolas published in 1998 in the {\it Journal of Number Theory}, if ${\cal B}$ is a subset of $\{1,2,\ldots,N\}$, there is a unique set ${\cal A}={\cal A}_0({\cal B},N)$ such that ${\cal A}\cap\{1,2,\dots ,N\}={\cal B}$ and $p({\cal A}, n)$ is even for $n>N$. In this paper we recall some properties of the sets ${\cal A}_0({\cal B},N)$, we describe the factorization into primes of the elements of the set ${\cal A}_0(\{1,2,3\},3)$, and prove that the number of elements of this set up to $x$ is asymptotically equivalent to $\ds c\frac{x}{(\log x)^{3/4}}$, where $c=0.937\ldots$. \medskip \ni {\bf R\'esum\'e.} Si ${\cal A}$ est un ensemble d'entiers positifs, nous noterons $p({\cal A}, n)$ le nombre de partitions de $n$ dont les parts sont dans ${\cal A}$. L'\'etude de la parit\'e de la fonction usuelle de partition $p(\N,n)$ (o\`u $\N$ est l'ensemble des entiers positifs) est un probl\`eme profond et difficile; mais il est facile de construire un ensemble ${\cal A}$ tel que le nombre $p({\cal A}, n)$ soit pair pour tout $n$ assez grand: dans un article paru au {\it Journal of Number Theory} en 1998, I.Z. Ruzsa, A. \sark et J.-L. Nicolas montrent que si ${\cal B}$ est un sous-ensemble de $\{1,2,\ldots,N\}$, il existe un seul ensemble ${\cal A}={\cal A}_0({\cal B},N)$ tel que ${\cal A}\cap\{1,2,\dots ,N\}={\cal B}$ et $p({\cal A}, n)$ est pair pour $n>N$. Dans cet article, nous rappelons quelques propri\'et\'es des ensembles ${\cal A}={\cal A}_0({\cal B},N)$, nous d\'ecrivons la d\'ecomposition en facteurs premiers des \'el\'ements de ${\cal A}_0(\{1,2,3\},3)$ et nous montrons que le nombre des \'el\'ements de cet ensemble inf\'erieurs \`a $x$ est \'equivalent \`a $\ds c\frac{x}{(\log x)^{3/4}}$, o\`u $c=0.937\ldots$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Introduction.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} %\markboth{\SMALL HELMUT PRODINGER}{\SMALL ON A FUNCTIONAL--DIFFERENCE %EQUATION} % % $\nb_0$ and $\nb$ denote the set of the non negative integers, resp. positive integers. ${\cal A}$ will denote a set of positive integers, and its counting function will be denoted by $A(x)$: $$\ds A(x)=|\{a:\ a\leq x\ ,\ a\in {\cal A}\}|.$$ %We shall also use the notation: %\begin{equation}\label{Aodd} %\ds A^{\textrm{odd}}(x)=|\{a:\ a\leq x\ ,a \textrm{ odd },\ a\in {\cal %A}\}|. %\end{equation} If ${\cal A}=\{a_1, a_2,\dots \}\subset \N$ (where $a_1N. \end{equation} then ${\cal A}$ is said to possess property $\ds P_i(N)$. If $i=0$ or $1$, ${\cal B}$ is a finite set of positive integers, and $N\in \N$ satisfying \begin{equation}\label{BN} {\cal B}=\{b_1,\dots ,b_k\}\not =\emptyset,\quad 0k_0$, we have $J_k=\emptyset$, $I_k=I_{k_0}$, $$q_k=q\stackrel{def}{=} \text{ lcm } (\be_1,\be_2, \ldots,\be_s)$$ and $q$ is a common period for all the sequences $\ds \left(\si(\ca,2^kn)\bmod 2^{k+1}\right)_{n\ge 1}$, $\;k\ge 0$. } \medskip {\bf Remark 1.} {\it In \cite{Ben4}, one can find examples of ${\cal B}$ and $N$ such that $q_0\ne q_1$. } \medskip Note that (\ref{conj}) was already proved for $k=0$ in \cite{NRS}, and for $k=1$ in \cite{Ben4}. By M\"obius inversion formula, (\ref{sig}) gives \begin{equation}\label{mob1} \ds n\chi({\cal A},n)=\sum_{d\dv n}\mu(d)\sigma({\cal A}, n/d) \end{equation} where $\mu$ is the M\"obius function. If $n$ is odd, by (\ref{conj}) with $k=0$, we know the value of $\sigma ({\cal A}, n) \bmod 2$, and this allows us from (\ref{mob1}) to determine $\chi({\cal A},n)$ for any set $\ca=\ca_i(\cb,N)$. This has been done in \cite{NS} for $\ca=\ca_0(\{1,2,3\},3)$ and in \cite{Ndeb} for $\ca=\ca_0(\{1,2,3,4,5\},5)$. In \cite{Ben4}, the validity of (\ref{conj}) for $k=1$ has been used to determine the elements of $\ca=\ca_0(\{1,2,3\},3)$ which are congruent to $2$ modulo $4$. Similarly, it is possible to deduce from (\ref{conj}) the value of $ \chi({\cal A},n)$ where $n$ is any positive integer. For that, it is convenient for $m$ odd to introduce the sum \begin{equation}\label{S} S(m,k)=\chi({\cal A},m)+2\chi({\cal A},2m)+\ldots+2^k\chi({\cal A},2^km). \end{equation} If $n$ writes $n=2^km$ with $k\ge 0$ and $m$ odd, (\ref{sig}) implies \begin{equation}\label{sigS} \sigma ({\cal A}, n)=\sigma ({\cal A}, 2^km)=\sum_{d\dv m} dS(d,k), \end{equation} which, by M\"obius inversion formula, gives \begin{equation}\label{mob2} mS(m,k)=\sum_{d\dv m} \mu(d) \sigma(\ca,n/d)=\sum_{d\dv \overline{m}} \mu(d) \sigma(\ca,n/d), \end{equation} where $\ds \;\overline{m}=\prod_{p\dv m}p\;$ denotes the radical of $m$. In the above sums, $n/d$ is always a multiple of $2^k$, so that, from (\ref{conj}) , the value of $\sigma(\ca,n/d)$ and thus the value of $S(m,k)$ are known modulo $2^{k+1}$. Therefore, from (\ref{S}), we can deduce the value of $\chi(\ca,2^im)$ for $i\le k$. In Section 4, by the above described method, the multiplicative structure of the elements of $\ca=\ca_0(\{1,2,3\},3)$ will be given (Theorem 2), with the surprising property that, for this set $\ca$, the $2$-adic expansion: \begin{equation}\label{2adic} 1+2\chi({\cal A},2)+4\chi({\cal A},4)+\ldots+2^k\chi({\cal A},2^k)+\ldots \end{equation} is one of the $2$-adic roots of the equation $x^2-x+2=0$. From Theorem 2, and from an extension of the so-called Selberg-Delange formula given in \cite{Ben}, we shall give in Section 5 (Theorem 3) an asymptotic estimation for $A(x)$: \begin{equation}\label{Ax} A(x)\sim c\frac{x}{(\log x)^{3/4}},\quad x\to\infty \end{equation} where $c$ is a constant the value of which is approximately $0.937$. The work done in Sections 3 and 4 for the set $\ca=\ca_0(\{1,2,3\},3)$ could be done, in principle, for any set $\ca=\ca_i(\cb,N)$. But, for technical reasons, the calculation can be difficult. We hope to return to this subject in an other article. We are pleased to thank M. Del\'eglise for computing the values of $A(x)$ (cf. Section 5), D. Barsky, K. Belabas and A. S\'ark\"ozy for several remarks. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ The Graeffe transformation.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let us consider the ring of formal power series $\C[[z]]$. For an element $$f(z)=a_0+a_1z+a_2z^2+\ldots+a_nz^n+\ldots$$ of this ring, the product $$f(z)f(-z)=b_0+b_1z^2+b_2z^4+\ldots+b_nz^{2n}+\ldots$$ is an even power series with \begin{equation}\label{Grco} b_0=a_0^2,\; b_1=2a_0a_2-a_1^2,\ldots,\; b_n=2\left(\sum_{i=0}^{n-1}(-1)^ia_ia_{2n-i} \right)+(-1)^na_n^2. \end{equation} We shall call $g=\cg(f)$ the series \begin{equation}\label{G} g(z)=\cg(f)(z)=b_0+b_1z+b_2z^2+\ldots+b_nz^{n}+\ldots. \end{equation} Note that we have \begin{equation}\label{gG} g(z^2)=\cg(f)(z^2)=f(z)f(-z). \end{equation} {\bf Example.} If $q$ is an odd integer and $f(z)=1-z^q$, we have $f(z)f(-z)=(1-z^q)(1+z^q)=1-z^{2q}$, and \begin{equation}\label{exam} \cg(f)=f. \end{equation} If $f$ is a polynomial of degree $n$ which does not vanish in $0$, and if $\widetilde f(z)=z^nf(1/z)$ is the reciprocal polynomial of $f$, then we have \begin{equation}\label{reci} \cg(\widetilde f)=(-1)^n\widetilde{\cg(f)}. \end{equation} It is obvious that, for any two series $f$ and $g$, the formulas \begin{equation}\label{prod} \cg(fg)=\cg(f)\cg(g) \end{equation} and, if $g(0)=1$, \begin{equation}\label{quo} \cg(f/g)=\cg(f)/\cg(g) \end{equation} hold. We shall often use the following notation for the iterates of $f$ by the transformation $\cg$: \begin{equation}\label{iter} f_0=f,\;\; f_1=\cg(f),\;\; f_2=\cg(f_1),\;\;\ldots,\;\; f_k=\cg(f_{k-1})=\cg^{(k)}(f),\ldots \end{equation} \medskip {\bf Proposition 1.} {\it Let $f$ be a polynomial of degree $n$ whose roots are $z_1$, $z_2,\ldots,z_n$ and leading coefficient is $a_n$. Then the polynomial $g=\cg(f)$, where $\cg$ is defined by (\ref{G}), has a leading coefficient equal to $(-1)^na_n^2$ and its roots are $z_1^2$, $z_2^2,\ldots,z_n^2$. } \medskip {\bf Proof.} From the relations $$f(z)=a_n(z-z_1)(z-z_2)\ldots(z-z_n)$$ and $$f(-z)=a_n(-z-z_1)(-z-z_2)\ldots(-z-z_n)$$ it follows that $$f(z)f(-z)=(-1)^na_n^2(z^2-z_1^2)(z^2-z_2^2)\ldots(z^2-z_n^2)$$ and therefore, from (\ref{gG}) \begin{equation}\label{Groot} g(z)=\cg(f)(z)=(-1)^na_n^2(z-z_1^2)(z-z_2^2)\ldots(z-z_n^2), \end{equation} which completes the proof of Proposition 1. $\Box$ In numerical analysis (cf. \cite{Gra}, \cite{Bare} or \cite{Ral}), the Graeffe method is used to compute an approximate value of the roots of a polynomial equation $f(x)=0$. The first step of the method is to calculate $f_k$ defined by (\ref{iter}) for $k$ large enough. From Proposition 1, the roots of $f_k$ are $z_1^{2^k},\ldots,z_n^{2^k}$, and, if we assume that $|z_1|>|z_2|>\ldots>|z_n|$, the sum of the roots of $f_k$ is close to $z_1^{2^k}$ which yields an approximate value for $|z_1|$. This old method is being revisited in the frame of computer algebra (cf. \cite{Gou}). \medskip {\bf Proposition 2.} {\it Let $f(z)\in \C[[z]]$, $f(0)\ne 0$,and \begin{equation}\label{prop21} z\frac{f'(z)}{f(z)}=\sum_{n=1}^\infty a_nz^n. \end{equation} Then, for $k\ge 1$, we have \begin{equation}\label{fkz} \sum_{n=1}^\infty a_{2^kn}z^n=z\frac{f_k'(z)}{f_k(z)}=\frac{z}{f_k(z)}\frac{d}{dz}f_k(z), \end{equation} where $f_k=\cg^{(k)}(f)$ is defined by (\ref{G}) and (\ref{iter}). } \medskip {\bf Remark 2.} {\it Here and in the sequence, $f_k'$ will denote the derivative of $f_k$ (and not the $k$-iterate of $f'$). } \medskip {\bf Proof.} We shall prove Proposition 2 by induction on $k$. For $k=1$ and $z=y^2$, we have from (\ref{prop21}) and (\ref{gG}) \begin{eqnarray}\label{prop2} \sum_{n=1}^\infty a_{2n}z^{n}&=& \sum_{n=1}^\infty a_{2n}y^{2n}=\frac 12\sum_{n=1}^\infty (a_{n}y^n+a_n(-y)^n)\nonumber\\ &=&\frac 12 \left( y\frac{f'(y)}{f(y)}-y\frac{f'(-y)}{f(-y)}\right)\ =\frac y2\frac{f'(y)f(-y)-f(y)f'(-y)}{f(y)f(-y)}\notag\\ &=&\frac{y}{2f_1(y^2)} \frac{d}{dy}f_1(y^2)= z\frac{f_1'(z)}{f_1(z)}. \end{eqnarray} Further, the induction on $k$ is easy, by substituting $a_{2^kn}$ to $a_{2n}$ and $f_{k-1}$ to $f$ in (\ref{prop2}). $\Box$ \bigskip {\bf Definition 2.} {\it We shall say that two power series $f,g$ with integral coefficients are congruent modulo $M$ (where $M$ is any positive integer) if their coefficients of same degree are congruent modulo $M$. In other words, if $$f(z)=a_0+a_1z+a_2z^2+\ldots+a_nz^n+\ldots\quad \in \Z[[z]]$$ and $$g(z)=b_0+b_1z+b_2z^2+\ldots+b_nz^{n}+\ldots\quad \in \Z[[z]]$$ then, \begin{equation}\label{cong} f\equiv g\pmod{M} \quad\Longleftrightarrow\quad \forall n\ge 0, \quad a_n\equiv b_n\pmod{M}. \end{equation} } Congruences of formal power series may be added or multiplied. If \begin{equation}\label{fg} f\equiv g\pmod{M} \end{equation} and $$u\equiv v \pmod{M},\qquad u\in\Z[[z]],\;\; v\in\Z[[z]]$$ then \begin{equation}\label{mufo} f+u\equiv g+v \pmod{M} \quad \textrm{ and } \quad fu\equiv gv \pmod{M}. \end{equation} You may derivate (\ref{fg}) and get \begin{equation}\label{cond} f'\equiv g'\pmod{M}. \end{equation} Moreover, if $f(0)=g(0)=1$, $1/f$ and $1/g$ have integer coefficients and we have, if (\ref{fg}) holds \begin{equation}\label{coni} \frac 1f \equiv \frac 1g \pmod{M}. \end{equation} It is also easy to see that, for $f\in\Z[[z]]$ and $\cg$ defined by (\ref{G}) we have \begin{equation}\label{Gcon} \cg(f)\equiv f \pmod{2}. \end{equation} \medskip {\bf Proposition 3.} {\it Let $f$ and $g$ be two formal power series with integral coefficients such that $f\equiv g\pmod{2}$. Then, for $k\ge 0$, we have \begin{equation}\label{con2k} f_k\equiv g_k \pmod{2^{k+1}}, \end{equation} where $f_k=\cg^{(k)}(f)$ and $g_k=\cg^{(k)}(g)$ are defined by (\ref{G}) and (\ref{iter}). } \medskip {\bf Proof.} Let us start by proving that if $u,v\in\Z[[z]]$ satisfy \begin{equation}\label{prop31} u\equiv v \pmod{2M} \end{equation} where $M$ is any positive integer, then $u_1=\cg(u)$ and $v_1=\cg(v)$ satisfy \begin{equation}\label{prop3} u_1\equiv v_1\pmod{4M}. \end{equation} It follows from (\ref{prop31}) that there exists $w\in\Z[[z]]$ such that $$u(z)=v(z)+2Mw(z).$$ Further, from (\ref{gG}) \begin{eqnarray*} u_1(z^2)&=&u(z)u(-z)=(v(z)+2Mw(z))(v(-z)+2Mw(-z))\\ &=&v_1(z^2)+2M[v(z)w(-z)+w(z)v(-z)]+4M^2w_1(z^2), \end{eqnarray*} where $w_1=\cg(w)$. But the above bracket is obviously congruent to $0$ modulo $2$ so that $$u_1(z^2)\equiv v_1(z^2)\pmod{4M}$$ which, by substituting $z$ to $z^2$, yields (\ref{prop3}). We shall prove Proposition 3 by induction on $k$. For $k=0$, from (\ref{iter}), (\ref{con2k}) is just our hypothesis $f\equiv g\pmod{2}$. Let us assume that (\ref{con2k}) holds for a non negative value of $k$; then applying (\ref{prop3}) with $u=f_k$, $v=g_k$ and $M=2^{k}$ will give $$f_{k+1}\equiv g_{k+1} \pmod{2^{k+2}}$$ and the proof of Proposition 3 is completed. $\Box$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The set ${\cal A}={\cal A}_0(\{1,2,3\},3)$.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In all this Section, $\ca$ will denote the set ${\cal A}_0(\{1,2,3\},3)$; we shall write $p(n), \si(n), \chi(n)$ instead of $p(\ca,n), \si(\ca,n), \chi(\ca,n)$ respectively. We shall recall in Lemma 1 some classical results on congruences modulo $2^k$. \medskip {\bf Lemma 1.} {\it Let $a,b$ and $c$ be integers. (i) If $a$ is odd and $k\ge 3$, the congruence \begin{equation}\label{le11} x^2\equiv a \pmod{2^k} \end{equation} has no solution if $a\not\equiv 1 \pmod{8}$, and has four solutions if $a\equiv 1 \pmod{8}$. Two of them satisfy \begin{equation}\label{le12} x^2\equiv a \pmod{2^{k+1}}. \end{equation} If $\rho_k$ is a solution of (\ref{le11}) which satisfies (\ref{le12}) then the four solutions of (\ref{le11}) are $\pm\rho_k$ and $\pm\rho_k+2^{k-1}$. By the method of Hensel, $\rho_k$ can be calculated by induction: if $\rho_k^2\equiv a+\vep 2^{k+1} \pmod{2^{k+2}}$, $\vep\in\{0,1\}$, then $\rho_{k+1}=\rho_k+\vep 2^{k+1}$. (ii) the congruence \begin{equation}\label{le13} x^2-x+a\equiv 0 \pmod{2^k} \end{equation} has no solution if $a$ is odd; if $a$ is even, it has two solutions, one is even and the other one is odd. They can be calculated by Hensel's method: if $\tau_k$ satisfies (\ref{le13}), then $\tau_{k+1}=\tau_k+ \vep 2^{k}$ is determined from \begin{equation}\label{le14} \vep\equiv \frac{\tau_k^2-\tau_k+a}{2^{k}} \pmod{2}. \end{equation} (iii) Any congruence $x^2+bx+c\equiv 0\pmod{2^k}$ can be put on the form (\ref{le11}) or (\ref{le13}) after a change of variable $y=x+\lfloor b/2\rfloor$. (iv) In the $2$-adic field $\Q_2$, the equation $x^2-a=0$ has two roots if and only if $a\equiv 1 \pmod{8}$. If $x_1$ and $x_2$ are the two solutions, we have $x_i\equiv \pm\rho_k \pmod{2^k}$. (v) In the $2$-adic field $\Q_2$, the equation $x^2-x+a=0$ has two roots $x_1$ and $x_2$ if and only if $a$ is even. Moreover, $x_i \bmod 2^k$ are solutions of (\ref{le13}). } \medskip {\bf Proof of (i).} It is a classical result that each odd residue class modulo $2^k$ for $k\ge 3$ can be written $\pm 5^\la$ with $0\le \la<2^{k-2}$. From this result, it is not difficult to prove (i). We may observe that, if $\rho$ is a solution of (\ref{le12}), $$(\pm\rho+2^{k-1})^2\equiv a+2^{k}\pmod{2^{k+1}}$$ so that $\pm\rho+2^{k-1}$ are solutions of (\ref{le11}) but not of (\ref{le12}). The Hensel method can be found in \cite{Bar} or \cite{Mig}. It can be accelerated to calculate $\rho_{k+1},\ldots,\rho_{2k-1}$ in terms of $\rho_k$. \medskip {\bf Proof of (ii).} If $\tau_k$ is a solution of (\ref{le13}), $\tau_k \bmod 2$ is a solution of $x^2-x+a\equiv 0 \pmod{2}$. But if $a$ is odd this last congruence has no solution while, if $a$ is even, it has two solutions $0$ and $1$. Both can be extended to solutions of (\ref{le13}), by using (\ref{le14}) with $k=1,2,\ldots$. An other possibility to solve (\ref{le13}) is to set $y=2x-1$. We have $y^2=4x^2-4x+1\equiv 1-4a \pmod{2^{k+2}}$. But the four solutions of this last congruence give only two solutions to (\ref{le13}). Since the sum of the two roots is $1$ they must have a different parity. To show (\ref{le14}), we calculate $$(\tau_k+\vep2^k)^2-(\tau_k+\vep 2^k)+a\equiv \tau_k^2-\tau_k+a -\vep 2^k\pmod{2^{k+1}}.$$ \medskip {\bf Proof of (iii).} It is obvious. \medskip {\bf Proof of (iv).} If $$x_1=\vep_0+\vep_1 2+\vep_2 2^2+\ldots+\vep_k 2^k+\ldots $$ is a $2$-adic solution of $x^2-a=0$, then, by writing $x_1=U_k+2^{k}R_k$, we have $U_k=x_1 \bmod 2^{k}$ and $x_1^2=a\equiv U_k^2 \pmod{2^{k+1}}$, so that $U_k$ satisfies (\ref{le11}) and (\ref{le12}) and thus, from (i), $U_k=\pm\rho_k$. In the other way, by the Hensel method, each root of (\ref{le11}) satisfying (\ref{le12}) can be extended in a $2$-adic solution. \medskip {\bf Proof of (v).} The proof of (v) looks like the one of (iv), but it is easier since (\ref{le13}) has only two solutions while (\ref{le11}) has four solutions, and the proof of Lemma 1 is completed. $\Box$ \medskip {\bf Theorem 1.} {\it Let ${\cal A}={\cal A}_0(\{1,2,3\},3)$. Then : (i) For all $k\geq 0$, the sequence $\ds\sigma( 2^kn)~\bmod 2^{k+1}$ is periodic in $n$ with period $q_k=7$. (ii) If $\ds u_k=\sigma(2^k)\bmod 2^{k+1} $ and $\ds v_k=\sigma(3.2^k) \bmod 2^{k+1}$ then \begin{equation}\label{4per} \ds\sigma( 2^kn)\equiv u_k, v_k,-3~(\bmod~2^{k+1}),~\hbox{respectively as}~\leg n7 =1,-1,0. \end{equation} where $\ds\leg n7$ is the Legendre symbol. (iii) $u_k$ and $v_k$ are the two solutions of the congruence \begin{equation}\label{congsd} x^2-x+2\equiv 0 ~(\bmod~2^{k+1}) \end{equation} and satisfy \begin{equation}\label{ukvk} u_k+v_k\equiv 1 \pmod{2^{k+1}}\quad\textrm{ and } \quad u_k\cdot v_k\equiv 2\pmod{2^{k+1}}. \end{equation} Moreover, if $k\ge r$, \begin{equation}\label{ukur} u_k\equiv u_r \pmod{2^{r+1}}. \end{equation} (iv) The equation \begin{equation}\label{eqsd} x^2-x+2=0 \end{equation} has two solutions in the $2$-adic field $\Q_2$; the odd one is \begin{equation}\label{x1} x_1=1+2+2^3+2^4+2^6+2^{13}+2^{14}+2^{18}+2^{19}+ 2^{22}+2^{25}+\ldots. \end{equation} We have \begin{equation}\label{ukx1} u_k\equiv x_1 \pmod{2^{k+1}}\, . \end{equation} Moreover, the elements of $\ca$ which are powers of $2$ are $1,2,2^3,2^4,2^6,2^{13},\ldots$; they are determined by \begin{equation}\label{2pk} x_1=\sum_{k=0}^\infty \chi(2^k)2^k. \end{equation} } \medskip {\bf Proof of (i).} The polynomial $P$ defined by (\ref{P0}) and (\ref{ep0}) is \begin{equation}\label{P3} P(z)=1+z+z^3 \end{equation} since $p(0)=1,p(1)=1,p(2)=2$ and $p(3)=3$. It is irreducible over $\F_2[z]$ so that, in (\ref{irr}), $s=1$ and $Q_1=P$. So, it follows from Theorem A that $\be_1=7$ and $q_k=7$ for all $k\ge 0$, which proves (i). \medskip {\bf Proof of (ii).} We shall denote by $H$ the other irreducible polynomial of degree $3$ over $\F_2[z]$, \begin{equation}\label{H3} H(z)=1+z^2+z^3. \end{equation} From (\ref{iter}) and Proposition 1, the leading coefficient of $P_k=\cg^{(k)}(P)$ is $-1$, and from (\ref{G}), (\ref{pA0}), (\ref{P0}) and (\ref{ep0}) \begin{equation}\label{Pk00} P_k(0)=1 \end{equation} so that we can write \begin{equation}\label{Pk4} P_k(z)=\cg^{(k)}(P)(z)= 1+a_kz+b_kz^2-z^3. \end{equation} Now, we observe that, from (\ref{P3}) and (\ref{H3}) the polynomials $P$ and $H$ are reciprocal. So, from (\ref{Pk4}) and (\ref{reci}) we have \begin{equation}\label{Hk4} H_k(z)=\cg^{(k)}(H)(z)=1-b_kz-a_kz^2-z^3. \end{equation} But we have \begin{equation}\label{cyclo} \frac{1-z^7}{1-z}=1+z+z^2+z^3+z^4+z^5+z^6\equiv P(z)H(z) \pmod{2}, \end{equation} and this implies, from (\ref{quo}), (\ref{exam}), (\ref{prod}) and Proposition 3 that \begin{equation}\label{cyclok} \hspace{-3mm}\frac{1-z^7}{1-z}=1+z+z^2+z^3+z^4+z^5+z^6\equiv P_k(z)H_k(z) \hspace{-3mm}\pmod{2^{k+1}}. \end{equation} By expanding the product $P_kH_k$ from (\ref{Pk4}) and (\ref{Hk4}), we get from (\ref{cyclok}) \begin{equation}\label{akbk} a_k-b_k\equiv 1 \pmod{2^{k+1}}\quad\textrm{ and } \quad a_k\cdot b_k\equiv -2\pmod{2^{k+1}}. \end{equation} By applying Proposition 2 to (\ref{FF}) (where $F(z)=F_\ca(z)$ is defined by (\ref{genF}), we get: \begin{equation}\label{FF3k} \sum_{n=1}^\infty \sigma (2^kn)z^n=z\frac{F_k'(z)}{F_k(z)} \end{equation} where $F_k$ is the $k$-iterate of $F$ by the transformation $\cg$ (cf. (\ref{iter})), and $\ds F_k'= \frac{d}{dz}(F_k(z))$. It follows from (\ref{genF}), (\ref{AiN}), (\ref{P0}) and (\ref{ep0}) that \begin{equation}\label{FconP} F\equiv P\pmod{2} \end{equation} and Proposition 3 implies that \begin{equation}\label{FkPk2k} F_k\equiv P_k \pmod{2^{k+1}} \end{equation} for all $k\ge 0$. We deduce from (\ref{Pk00}) and (\ref{FkPk2k}) that \begin{equation}\label{Pk0} F_k(0)=P_k(0)=1 \end{equation} and thus, from (\ref{mufo}), (\ref{cond}) and (\ref{coni}), (\ref{FkPk2k}) implies \begin{equation}\label{Pk} z\frac{F_k'(z)}{F_k(z)}\equiv z\frac{P_k'(z)}{P_k(z)} \pmod{2^{k+1}}. \end{equation} Therefore, from (\ref{FF3k}) and (\ref{Pk}), it follows: \begin{equation}\label{FP3k} \sum_{n=1}^\infty \sigma (2^kn)z^n\equiv z\frac{P_k'(z)}{P_k(z)} \pmod{2^{k+1}}. \end{equation} From (\ref{FP3k}) and (\ref{cyclok}), we have \begin{equation}\label{si4} \sum_{n=1}^\infty \si(2^kn)z^n\equiv z\frac{P_k'(z)}{P_k(z)} \equiv z\frac{(1-z)P_k'(z)H_k(z)}{1-z^7}\pmod{2^{k+1}}. \end{equation} The expansion of the numerator of the right hand side of (\ref{si4}) from (\ref{Pk4}), (\ref{Hk4}) and (\ref{akbk}) yields \begin{eqnarray}\label{expa} z(1-z)P_k'(z)H_k(z)\equiv\hspace{5cm}& &\\ a_kz+a_kz^2-b_kz^3+a_kz^4-b_kz^5-b_kz^6-3z^7 & &\hspace{-5mm}\pmod{2^{k+1}}.\notag \end{eqnarray} By expanding the denominator of the right hand side of (\ref{si4}) :$\ds \frac{1}{1-z^7}=1+z^7+z^{14}+\ldots$, it follows from (\ref{si4}) and (\ref{expa}) that \begin{equation}\label{cong4} \left. \begin{array}{rccccccc} \si(2^kn)\equiv& a_k&a_k&-b_k&a_k&-b_k&-b_k&-3\pmod{2^{k+1}}\\ \hbox{ resp. as }n\equiv& 1&2&3&4&5&6&0\pmod{7}. \end{array}\right\} \end{equation} The congruences (\ref{cong4}) give for $n=1$ and $n=3$ \begin{equation}\label{con134} u_k=\si(2^k)\equiv a_k \hspace{-2mm}\pmod{2^{k+1}}\textrm{ and } v_k\equiv \si(3\cdot 2^k)\equiv -b_k \hspace{-2mm}\pmod{2^{k+1}}. \end{equation} Since the quadratic residue classes modulo $7$ are $1,2$ and $4$, (\ref{cong4}) and (\ref{con134}) prove (ii). \medskip {\bf Proof of (iii).} Formula (\ref{ukvk}) follows from (\ref{akbk}) and (\ref{con134}), and yields $u_k(1-u_k)\equiv 2\pmod{2^{k+1}}$; so, $u_k$ is a solution of the congruence (\ref{congsd}). By the same way $v_k$ can be proved to be also a solution of (\ref{congsd}). Finally, if $k\ge r$, $$u_k=\si(2^k)=u_r+\sum_{j=r+1}^k \chi(2^j)2^j \equiv u_r\pmod{2^{r+1}},$$ which shows (\ref{ukur}) and completes the proof of (iii). \medskip {\bf Proof of (iv).} Note that $u_k=\si(2^k)$ is odd (since $1\in\ca$) while $v_k$ is even (since $1,3 \in\ca$). Since its discriminant $-7$ is congruent to $1$ modulo $8$ (cf. Lemma 1), the equation (\ref{eqsd}) has two roots in $\Q_2$, $x_1\equiv 1\pmod{2}$ and $x_2\equiv 0\pmod{2}$. Moreover, $x_1 \bmod 2^{k+1}$ is solution of (\ref{congsd}), and as it is smaller than $2^{k+1}$ (like $u_k$) it is equal to $u_k$ (because $u_k\equiv 1\pmod{2}$) and so, (\ref{ukx1}) is proved. Similarly, $v_k=x_2 \bmod 2^{k+1}$. The expansion (\ref{x1}) has been calculated with the function {\it polrootspadic} of PARI. The expansion of $x_2$ is \begin{equation}\label{x2} x_2=2+2^2+2^5+2^7+2^8+2^9+2^{10}+2^{11}+2^{12}+2^{15}+2^{16}+\ldots . \end{equation} At the exception of $2^1$, the powers of $2$ appear either in $x_1$ or in $x_2$; the reason is that $$x_1+x_2=1=2+\frac{1}{1-2}=2+\sum_{n=0}^\infty 2^n.$$ Since $u_k$ has been defined as equal to $\ds \si(2^k)=\sum_{i=0}^k \chi(2^i)2^i$, (\ref{2pk}) follows from (\ref{ukx1}) and this completes the proof of Theorem 1. $\Box$ \medskip \begin{center} {\bf Numerical table} \end{center} $$ \begin{array}{c|cccccccccccccc|} k=& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9 &10&11&12&13\\ \hline u_k=&1&3&3&11&27&27&91&91&91&91&91&91&91&8283\\ v_k=&0&2&6&6&6&38&38&166&422&934&1958&4006&8102&8102\\ \hline \end{array} $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The elements of ${\cal A}={\cal A}_0(\{1,2,3\},3)$.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \medskip Let us define two classical arithmetic functions. If $n$ is a positive integer, $\om(n)$ will denote the number of distinct primes dividing $n$ while $\Om(n)$ will be the number of primes dividing $n$ according to multiplicity. We are now ready to state Theorem 2 which gives the multiplicative structure of the elements of $\ca$. \medskip {\bf Theorem 2.} {\it Let ${\cal A}={\cal A}_0(\{1,2,3\},3)$. Then : (i) The elements of $\ca$ of the form $2^k$ are determined by Theorem 1 (iv). Similarly, the elements of $\ca$ of the form $7\cdot 2^k$ are determined by the even solution $x_7$ of the $2$-adic equation $7x^2+7x+2=0$ \begin{eqnarray}\label{x7} x_7&=&\sum_{k=0}^\infty \chi(7\cdot 2^k)2^k\\ &=& 2 + 2^2 + 2^3 + 2^6 + 2^7 + 2^9 + 2^{10} + 2^{12} + 2^{16} + 2^{18} + 2^{20} + 2^{21}+\ldots \notag %+ 2^22 + 2^23 + 2^24 + 2^26 + 2^27 %+ 2^28 + 2^29 + 2^31 + 2^32 +\ldots \end{eqnarray} (ii) Let $p$ be an odd prime congruent to $1,2$ or $4$ modulo $7$ (i.e.,$\leg p7 =1$). Then $(p,a)=1$ for all $ a\in \ca$. (iii) If $n\in\nb$ and $49$ divides $n$, then $n\notin {\cal A}$. (iv) Let $n=2^km$, and \begin{equation}\label{mh} m=p_1^{\la_1}p_2^{\la_2}\ldots p_h^{\la_h} \end{equation} where $p_i$ are primes, distinct and congruent to $3,5$ or $6$ modulo $7$ and $\la_i$ are positive integers. We assume that $h=\om(m)\ge 1$ (i.e. $m\ne 1$) and recall that $\Om(m)=\la_1+\ldots+\la_h$. $\bullet$ (a) If $k\le h-2$, then $n\notin \ca$ and $7n\notin \ca$. $\bullet$ (b) If $k= h-1$, then, without any restriction, $n\in \ca$ and $7n\in \ca$. $\bullet$ (c) If $k= h-1+r$, with $r\ge 1$, then $n\in \ca$ if and only if \begin{equation}\label{OM} m\equiv (-1)^{\Om(m)}(1-2u_r)\ell^{-1} \pmod{2^{r+1}}, \quad \ell=1,3,5,\ldots, 2^r-1. \end{equation} Moreover, the expansion \begin{equation}\label{xm} x_m=1+\chi(2^hm)2+\chi(2^{h+1}m)2^2+\ldots +\chi(2^{h+j}m)2^{j+1}+\ldots \end{equation} is one of the two $2$-adic solutions of the equation \begin{equation}\label{2adeq} m^2x^2+7=0. \end{equation} $\bullet$ (d) If $k= h-1+r$, with $r\ge 1$, then $7n\in \ca$ if and only if \begin{equation}\label{OM7} m\equiv (-1)^{\Om(m)}(2u_r-1)7^{-1}\ell^{-1} \hspace{-3mm}\pmod{2^{r+1}}, \; \ell=1,3,5,\ldots, 2^r-1. \end{equation} Moreover, the expansion \begin{equation}\label{xm7} x_{7,m}=1+\chi(7\cdot 2^hm)2+\ldots +\chi(7\cdot 2^{h+j}m)2^{j+1}+\ldots \end{equation} is one of the two $2$-adic solutions of the equation \begin{equation}\label{2adeq7} 7m^2x^2+1=0. \end{equation} We may observe that for $k=0,1,2$, we have for $m$ odd, $m\ne 1$ \begin{equation}\label{iff} n=2^km\in \ca \Longleftrightarrow 7n=7\cdot 2^km\in \ca. \end{equation} } %\medskip {\bf Remark 3.} {\it Theorem 2 has been proved for $k=0$ in \cite{NS} and for $k=1$ in \cite{Ben4}.} \medskip {\bf Proof of (i).} From (\ref{S}), we have \begin{equation}\label{Sk} S(7,k)=\chi(7)+\chi(7\cdot 2)2+\ldots +\chi(7\cdot2^k)2^k \end{equation} and by (\ref{mob2}) and (\ref{4per}) \begin{eqnarray}\label{401} 7S(7,k)&=&\sum_{d\dv 7}\mu(d)\si\left(\frac{7\cdot 2^k}{d}\right)\notag\\ &=&\si(7\cdot 2^k)-\si(2^k)\equiv -3-u_k \pmod{2^{k+1}}, \end{eqnarray} so that $S(7,k)\equiv (-3-u_k)7^{-1} \pmod{2^{k+1}}$. Since, from Theorem 1 (iii), $u_k$ is solution of (\ref{congsd}), a simple calculation shows that $S(7,k)$ is a solution of $7x^2+7x+2\equiv 0 \pmod{2^{k+1}}$. From (\ref{4per}), $\si(7)=1+7\chi(7)\equiv -3\pmod{2}$ so that $\chi(7)=0$ and, from (\ref{Sk}), $S(7,k)$ is even, which proves (i). \medskip {\bf Proof of (ii).} Let us suppose that $n=2^km\in \ca$, $m$ odd and multiple of a prime $p\equiv 1,2,4\pmod{7}$. Here we have from (\ref{S}) \begin{equation}\label{Skp} S(m,k)=\chi(m)+\chi(2m)2+\ldots +\chi(2^km)2^k<2^{k+1}. \end{equation} We get from (\ref{mob2}) \begin{equation}\label{402} mS(m,k)=\sum_{d\dv \overline{m}}\mu(d)\si\left(\frac nd\right)=\hspace{-2mm} \sum_{d\dv (\overline{m}/p)}\mu(d)\left[\si\left(\frac nd\right)-\si\left(\frac {n}{pd}\right)\right]. \end{equation} But, from (\ref{4per}), the above bracket is congruent to $0$ modulo $2^{k+1}$, since $\ds \leg{n/d}{7} =\leg{n/pd}{7}\times\leg p7=\leg{n/pd}{7}$. This implies that $S(m,k)$ is congruent to $0$ modulo $2^{k+1}$, and as $0\le S(m,k)<2^{k+1}$, $S(m,k)$ vanishes and, from (\ref{Skp}), $\chi(n)=\chi(2^km)$ also vanishes which proves (ii). \medskip {\bf Proof of (iii).} Let us now suppose that $n=2^km\in \ca$, $m$ odd and multiple of $49$. If we define $S(m,k)$ by (\ref{Skp}), (\ref{402}) still holds if we replace $p$ by $7$. Now, in the bracket, both $\frac nd$ and $\frac {n}{7d}$ are multiple of $7$, so that, from (\ref{4per}), again the bracket is congruent to $0$ modulo $2^{k+1}$. The proof of (iii) ends in the same terms than the one of (ii) above. \medskip {\bf Proof of (iv).} We shall need the following lemma: \medskip {\bf Lemma 2.} {\it With $m,n,h,k$ as in Theorem 2 (iv), $u_k$ as defined in Theorem 1, $S(m,k)$ as defined by (\ref{Skp}) (or \ref{S}), we have \begin{equation}\label{Smk} mS(m,k)\equiv 2^{h-1}(2u_k-1)(-1)^{\Om(m)} \pmod{2^{k+1}}, \end{equation} and \begin{equation}\label{Smk7} 7mS(7m,k)\equiv -2^{h-1}(2u_k-1)(-1)^{\Om(m)} \pmod{2^{k+1}}. \end{equation} } %\medskip {\bf Proof of Lemma 2.} With $n=2^km$, we have from (\ref{mob2}), \begin{equation}\label{le21} mS(m,k)=\sum_{d\dv \overline{m}}\mu(d)\si\left(\frac nd\right)= \sum_{\substack{d\dv \overline{m} \\ \mu(d)=1}}\si\left(\frac nd\right)- \sum_{\substack{d\dv \overline{m} \\ \mu(d)=-1}}\si\left(\frac nd\right) \end{equation} with $\overline{m}=p_1\ldots p_h$. Since $\leg 27=1$ and $\leg{p_i}{7}=-1$, we have $$\leg n7=(-1)^{\Om(m)}\quad \text{ and } \quad \leg{n/d}{7}=(-1)^{\Om(m)}\mu(d).$$ Let us assume that $\Om(m)$ is even; then we get from (\ref{le21}) and (\ref{4per}) \begin{equation}\label{le22} mS(m,k)\equiv u_k\left(\sum_{\substack{d\dv \overline{m} \\ \mu(d)=1}} 1\right)- v_k\left(\sum_{\substack{d\dv \overline{m} \\ \mu(d)=-1}}1\right)\pmod{2^{k+1}}. \end{equation} The first (resp. second) sum is the number of subsets of $\{1,2,\ldots,h\}$ with an even (resp. odd) cardinal; they are both equal to $2^{h-1}$ (since $h\ge 1$), and from (\ref{ukvk}), (\ref{le22}) yields \begin{equation}\label{Smmk} mS(m,k)\equiv 2^{h-1}(2u_k-1) \pmod{2^{k+1}}. \end{equation} If $\Om(m)$ is odd, the same calculation leads to a formula looking like (\ref{Smmk}) where $(2u_k-1)$ is replaced by $(1-2u_k)$ so that, in both cases, (\ref{Smk}) is proved. With $n$ still being equal to $2^km$, we have from (\ref{mob2}) \begin{equation}\label{le23} 7mS(7m,k)=\!\!\!\sum_{d\dv (7\overline{m})}\mu(d)\si\left(\frac{7n}{d}\right)=\hspace{-2mm} \sum_{d\dv \overline{m}}\mu(d)\si\left(\frac{7n}{d}\right) \!\!-\hspace{-2mm}\sum_{d\dv \overline{m}}\mu(d) \si\left(\frac {n}{d}\right). \end{equation} But, $7n/d\equiv 0 \pmod{7}$ so that, by (\ref{4per}), $\ds \si\left(\frac{7n}{d}\right) \equiv -3 \pmod{2^{k+1}}$ and since $\overline{m}\ne 1$, $\ds \sum_{d\dv \overline{m}}\mu(d)=0$. Therefore, it follows from (\ref{le23}) and (\ref{le21}) that \begin{equation}\label{le24} 7mS(7m,k)\equiv -\sum_{d\dv \overline{m}}\mu(d) \si\left(\frac {n}{d}\right)\equiv -mS(m,k) \pmod{2^{k+1}}, \end{equation} which, together with (\ref{Smk}) proves (\ref{Smk7}). $\Box$ \medskip Let us prove now Theorem 2 (iv): \medskip {\bf Proof of (iv) (a).} If $k\le h-2$, it follows from Lemma 2 (\ref{Smk}) that $$S(m,k)\equiv 0\pmod{2^{k+1}}.$$ From (\ref{Skp}), this implies $S(m,k)=0$ (since $0\le S(m,k)<2^{k+1}$), and, therefore, $\chi(n)=\chi(2^kn)=0$, i.e. $n\notin \ca$. By using (\ref{Smk7}) instead of (\ref{Smk}), it can be proved in the same way that $\chi(7n)=0$, i.e. $7n\notin \ca$. \medskip {\bf Proof of (iv) (b).} If $k= h-1$, (\ref{Smk}) writes \begin{equation}\label{iva1} mS(m,k)\equiv 2^{k}(2u_k-1)(-1)^{\Om(m)} \pmod{2^{k+1}} \end{equation} so that $S(m,k)$ is a multiple of $2^k$, and, by dividing (\ref{iva1}) by $2^k$, $S(m,k)/2^k$ is odd. But then, from (\ref{Skp}), $S(m,k)=2^k\chi(2^km)=2^k\chi(n)$ and thus $\chi(n)=1$ and $n\in\ca$. A similar proof shows that $7n\in\ca$. \medskip {\bf Proof of (iv) (c).} It follows from (\ref{Smk}) that $S(m,k)$ is a multiple of $2^{h-1}$ and by dividing (\ref{Smk}) by $2^{h-1}$ and using (\ref{ukur}), we get \begin{equation}\label{ivc1} m\frac{S(m,k)}{2^{h-1}}\equiv (2u_k-1)(-1)^{\Om(m)}\equiv (2u_r-1)(-1)^{\Om(m)} \pmod{2^{r+1}}. \end{equation} But, from (\ref{Skp}), we have \begin{equation}\label{ivc2} \frac{S(m,k)}{2^{h-1}}=1+\chi(2^hm)2+\ldots+\chi(2^km)2^r, \end{equation} since, by (b), $\chi(2^{h-1}m)=1$. Let $x$ be the solution of the congruence \begin{equation}\label{ivc3} mx\equiv -(2u_r-1)(-1)^{\Om(m)} \pmod{2^{r+1}}, \end{equation} satisfying $0\le x<2^{r+1}$; then, from (\ref{ivc1}), $2^{r+1}-x$ is equal to $\ds \frac{S(m,r)}{2^{h-1}}$. So, if $x<2^r$, it follows from (\ref{ivc2}) that $\chi(n)=\chi(2^km)=1$ while, if $x>2^r$, $\chi(n)=0$. Since $u_k$ satisfies (\ref{congsd}), \begin{equation}\label{ivc4} \left((2u_r-1)(-1)^{\Om(m)}\right)^2=4u_r^2-4u_r+1\equiv -7 \pmod{2^{r+3}} \end{equation} and, so, from (\ref{ivc1}), $\ds \frac{S(m,r)}{2^{h-1}}$ is a solution of $m^2x^2+7\equiv 0 \pmod{2^{r+3}}$, and thus, from (\ref{ivc2}) and Lemma 1, $x_m$ is a solution of the $2$-adic equation (\ref{2adeq}). By using (\ref{OM}) with $r=1$ we know that $2^hm\in \ca$ if and only if\\ $m(-1)^{\Om(m)}\equiv 3 \pmod{4}$. Thus \begin{equation}\label{ivc5} \chi(2^hm)\equiv \frac{(-1)^{\Om(m)}m-1}{2}\pmod{2} \end{equation} which allows us to distinguish for $x_m$ between the two roots of (\ref{2adeq}). \medskip {\bf Proof of (iv) (d).} It is the same proof than the proof of (c). We just have to show (\ref{iff}), which follows immediately from (\ref{OM}) and (\ref{OM7}) by noting that $7^{-1}\equiv -1\pmod{8}$. In particular, for $r=1$, (\ref{OM}) and (\ref{OM7}) co\"{\i}ncide so that $\chi(7\cdot2^hm)=\chi(2^hm)$, and thus, formula (\ref{ivc5}) still holds when replacing $\chi(2^hm)$ by $\chi(7\cdot2^hm)$. $\Box$ \medskip If $m=p_1^{\la_1}\ldots p_h^{\la_h}$, for $r\le 5$, (\ref{OM}) and (\ref{OM7}) can be written as $$\chi(2^hm)=\chi(7\cdot2^hm)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 3\pmod{4}$$ $$\chi(2^{h+1}m)=\chi(7\cdot2^{h+1}m)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 1,3\pmod{8}$$ $$\chi(2^{h+2}m)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 9, 11, 13, 15\pmod{16}$$ $$\chi(7\cdot2^{h+2}m)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 1, 3, 5, 7\pmod{16}$$ $$\chi(2^{h+3}m)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 1, 5, 11, 15, 19, 23, 25, 29 \pmod{32}$$ $$\chi(7\cdot2^{h+3}m)=1\Longleftrightarrow\; (-1)^{\Om(m)}m\equiv 1, 3, 5, 7,9,11,13,15\pmod{32}$$ \begin{eqnarray*} \chi(2^{h+4}m)&=&1\Longleftrightarrow\\ (-1)^{\Om(m)}m&\equiv& 1, 3, 5, 7, 11, 15, 17, 21, 25, 27, 29, 31, 41, 45, 51, 55 \pmod{64} \end{eqnarray*} \begin{eqnarray*} \chi(7\cdot2^{h+4}m)&=&1\Longleftrightarrow\\ (-1)^{\Om(m)}m&\equiv&\hspace{-3mm} 5, 7, 9, 11, 21, 23, 25, 27, 33, 35, 45, 47, 49, 51, 61, 63\hspace{-3mm} \pmod{64}. \end{eqnarray*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Estimation of $A(x)$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this Section, we want to estimate $A(x)$ where $\ca$ will denote the set ${\cal A}_0(\{1,2,3\},3)$; in view of using the description of the elements of $\ca$ given in Theorem 2, we need some definitions. Let us denote by $\cf$ the set of the integers \begin{equation}\label{6F} n=2^hp_1^{\la_1}p_2^{\la_2}\ldots p_h^{\la_h},\quad h\ge 1, \quad p_i\equiv 3,5,6\pmod{7}. \end{equation} The elements of $\cf$ are \begin{equation}\label{6Fs} \cf=\{6,10,18,26,34,38,50,54,60,62,82,94,\ldots\}. \end{equation} In \cite{Ben}, it has been proved that the asymptotic equivalence \begin{equation}\label{6Fx} F(x)=|\{n\in \cf; n\le x\}|\sim \ga \frac{x}{(\log x)^{3/4}} \end{equation} holds for $x\to\infty$, with \begin{equation}\label{6gam} \ga=\frac{1}{4\Ga(5/4)}\left(\frac{6}{\pi\sqrt7}\right)^{1/4}\ga_1 \end{equation} and \begin{equation}\label{6gam1} \ga_1= \prod_{p\equiv 3,5,6\hspace{-2mm}\pmod{7}} \left(\left(1+\frac{1}{2p-2}\right) \left(1-\frac{1}{p}\right)^{1/2} \left(1-\frac{1}{p^2}\right)^{-1/4}\right). \end{equation} Calculating the product (\ref{6gam1}) with the primes up to $100000$ yields for $\ga_1$ the approximate value $1.07517$. Note that, with the method described in \cite{Coh}, it is possible to calculate $\ga_1$ with a very high precision. From $\Ga(5/4)=0.906402$ and (\ref{6gam}) the approximate value of $\ga$ is \begin{equation}\label{6gnum} \ga=0.2733. \end{equation} If $\de(n)$ is the characteristic function of $\cf$, the Dirichlet's series $\ds \sum_{n=1}^\infty \frac{\de(n)}{n^s}$ has an Eulerian product for $\Re s>1$ \begin{eqnarray}\label{6Dir} \sum_{n=1}^\infty \frac{\de(n)}{n^s}&=&\prod_{p\equiv 3,5,6\hspace{-2mm} \pmod{7}} \left(1+\frac{1}{(2p)^s}+\frac{1}{2^sp^{2s}}+\ldots +\frac{1}{2^sp^{ks}}+\ldots\right)\notag\\ &=&\prod_{p\equiv 3,5,6\hspace{-2mm}\pmod{7}}\left(1+\frac{1}{2^s(p^s-1)}\right). \end{eqnarray} In \cite{Ben}, the proof of (\ref{6Fx}) starts from formula (\ref{6Dir}). For $i=0$ or $1$, $\ell$ odd, and $r\ge 0$ we define \begin{equation}\label{6Filr} \cf_{i;\ r,\ \ell}= \{2^hm\in \cf,\quad \Om(m)\equiv i\pmod{2},\quad m\equiv \ell \pmod{2^{r+1}}\}. \end{equation} It has been proved in \cite{Ben} that for $r$ fixed, and $x$ going to infinity, we have for any $i$ and $\ell$ \begin{equation}\label{6Fix} F_{i;\ r,\ \ell}(x)=|\{n\in \cf_{i;\ r,\ \ell}\:\: , \;\; n\le x\}|\sim \frac{\ga}{2^{r+1}}\frac{x}{(\log x)^{3/4}}\cdot \end{equation} From (\ref{6Fx}), (\ref{6Fix}) and Theorem 2, we shall prove \medskip {\bf Theorem 3.} {\it Let $\ca={\cal A}_0(\{1,2,3\},3)$. The number $A(x)$ of elements of $\ca$ up to $x$ satisfies, when $x$ tends to infinity: \begin{equation}\label{6t} A(x)\sim \frac{24\ga}{7} \frac{x}{(\log x)^{3/4}} \end{equation} where $\ga$ is defined by (\ref{6gam}); an approximate value of $24\ga/7$ is $0.937$. } \medskip {\bf Proof. } Let $\ca'$ be the subset of $\ca$ whose elements are of the form $2^k$ or $7\cdot 2^k$. The number of such elements up to $x$ is clearly \begin{equation}\label{6A'} A'(x)=O(\log (x)),\quad x\to\infty. \end{equation} Now, it follows from Theorem 2 (i) and (iv) that \begin{equation}\label{6Ar} \ca=\ca'\cup\;\;\bigcup_{r=0}^\infty \left(\ca^{(r)}\cup\ca^{(r,7)}\right) \end{equation} where the elements of $\ca^{(r)}$ are the $n$'s, $n\in \ca$, $n=2^{h-1+r}p_1^{\la_1}\ldots p_h^{\la_h}$ and similarly, the elements of $\ca^{(r,7)}$ are the $n$'s, $n\in \ca$, $n=7\cdot 2^{h-1+r}p_1^{\la_1}\ldots p_h^{\la_h}$. From Theorem 2 (iv) (b) it follows that for $r=0$, \begin{equation}\label{6rz} \ca^{(0)}=\frac 12 \cf \quad \textrm{ and } \quad A^{(0)}(x)=F(2x), \end{equation} and \begin{equation}\label{6rz7} \ca^{(0,7)}=\frac 72 \cf \quad \textrm{ and } \quad A^{(0,7)}(x)=F\left(\frac{2x}{7}\right). \end{equation} In the same way, if $a^{-1}$ denotes an inverse of $a$ modulo $2^{r+1}$, Theorem 2 (iv) (c) and (d) implies for $r\ge 1$ \begin{equation}\label{6r} \hspace{-2mm}A^{(r)}(x)=\hspace{-2mm}\sum_{\ell\in \{1,3,\ldots, 2^r-1\}} \hspace{-2mm}\left( F_{0;\ r,\ (1-2u_r)\ell^{-1} }\left(\frac{x}{2^{r-1}}\right) \!\!+\!\!F_{1;\ r,\ (2u_r-1)\ell^{-1} }\left(\frac{x}{2^{r-1}}\right) \!\right) \end{equation} and \begin{eqnarray}\label{6r7} A^{(r,7)}(x)&=&\sum_{\ell\in \{1,3,\ldots, 2^r-1\}} F_{0;\ r,\ (2u_r-1)(7\ell)^{-1} }\left(\frac{x}{7\cdot 2^{r-1}}\right)\notag\\ &+&\sum_{\ell\in \{1,3,\ldots, 2^r-1\}} F_{1;\ r,\ (1-2u_r)(7\ell)^{-1} }\left(\frac{x}{7\cdot 2^{r-1}}\right). \end{eqnarray} It also follows from Theorem 2 that, for any $r\ge 0$, $\ca^{(r)}\subset 2^{r-1}\cf$ and $\ca^{(r,7)}\subset 7\cdot 2^{r-1}\cf$ so that \begin{equation}\label{6rM} A^{(r)}(x)\le F\left(\frac{x}{2^{r-1}}\right)\quad \textrm{ and } \quad A^{(r,7)}(x)\le F\left(\frac{x}{7\cdot 2^{r-1}}\right)\le F\left(\frac{x}{2^{r-1}}\right). \end{equation} Moreover, from (\ref{6Fx}) and (\ref{6Fs}), there exists an absolute constant $K$ such that \begin{equation}\label{6FxM} F(x)\le K \frac{x}{(\log x)^{3/4}}\quad \text{ for } x>1 \textrm{ and } F(x)=0 \quad \text{ for } x< 6. \end{equation} It follows from (\ref{6rM}) and (\ref{6FxM}) that $A^{(r)}(x)= A^{(r,7)}(x)=0$ for $\ds r>\frac{\log(x/3)}{\log 2}$ so that (\ref{6Ar}) implies \begin{equation}\label{6Aso} A(x)=A'(x)+\sum_{r=0}^{R''} \left( A^{(r)}(x)+A^{(r,7)}(x)\right), \quad R''=\left\lfloor\frac{\log(x/3)}{\log 2}\right\rfloor. \end{equation} Now, we cut the sum (\ref{6Aso}) in three parts: \begin{equation}\label{6par} A(x)=A'(x)+\sum_{r=0}^R+\sum_{r=R+1}^{R'}+\sum_{r=R'+1}^{R''} \stackrel{def}{=} A'(x)+S+S'+S'', \end{equation} where $R$ is a large but fixed integer, and $R'$ is defined by $2^{R'-1}\le \sqrt x<2^{R'}$. We have from (\ref{6rM}) $$S''=\sum_{r=R'+1}^{R''} \left( A^{(r)}(x)+A^{(r,7)}(x)\right)\le 2\sum_{r=R'+1}^{R''} F\left(\frac{x}{2^{r-1}}\right)\; ;$$ and, by observing that, for $r\le R''$, $\ds \frac{x}{2^{r-1}}\ge 6$, we get from (\ref{6FxM}) \begin{equation}\label{6S''} S''\le 2K\sum_{r=R'+1}^{R''}\frac{x}{(2^{r-1})(\log 6)^{3/4}} \le \frac{2Kx}{2^{R'-1}}\le 4K\sqrt x. \end{equation} Similarly, we get \begin{eqnarray}\label{6S'} S'&=&\sum_{r=R+1}^{R'} \left( A^{(r)}(x)+A^{(r,7)}(x)\right)\le 2\sum_{r=R+1}^{R'} F\left(\frac{x}{2^{r-1}}\right)\notag\\ &\le& 2K\sum_{r=R+1}^{R'}\frac{x}{(2^{r-1})(\log(x/2^{R'-1}))^{3/4}} \le 2K\sum_{r=R+1}^{R'}\frac{x}{2^{r-1}(\log\sqrt x)^{3/4}} \notag\\ &\le& 2^{1+3/4}K\frac{x}{(\log x)^{3/4}}\sum_{r=R+1}^{\infty}\frac{1}{2^{r-1}} \le \frac{8K}{2^R}\frac{x}{(\log x)^{3/4}}\cdot \end{eqnarray} We deduce from (\ref{6r}), (\ref{6r7}) and (\ref{6Fix}) that, for $r\ge 1$ and $r$ fixed, \begin{equation}\label{6req} A^{(r)}(x)\sim\frac{\ga}{2^{r}}\frac{x}{(\log x)^{3/4}} \;\; \textrm{ and } \;\; A^{(r,7)}(x)\sim\frac{\ga}{7\cdot2^{r}}\frac{x}{(\log x)^{3/4}} \;\; (x\to\infty). \end{equation} Since $R$ is fixed, we get from (\ref{6rz}), (\ref{6rz7}), (\ref{6Fx}) and (\ref{6req}) for $x$ tending to infinity \begin{eqnarray}\label{6S} S&=&A^{(0)}(x)+A^{(0,7)}(x)+\sum_{r=1}^{R} \left( A^{(r)}(x)+A^{(r,7)}(x)\right)\notag\\ &\sim& \frac {8\ga }{7} \frac{x}{(\log x)^{3/4}} \left(2+\sum_{r=1}^{R}\frac{1}{2^{r}}\right)= \frac {8\ga }{7}\left(3-\frac{1}{2^{R}}\right) \frac{x}{(\log x)^{3/4}}. \end{eqnarray} By making $R$ going to infinity, (\ref{6t}) follows from (\ref{6par}), (\ref{6A'}), (\ref{6S''}), (\ref{6S'}) and (\ref{6S}) and the proof of Theorem 3 is completed. $\Box$ The following table has been calculated by M. Del\'eglise by using the multiplicative structure of the elements of $\ca=\ca_0(\{1,2,3\}),3)$ given by Theorem 2. The last line is the asymptotic result of Theorem 3. \medskip \begin{center} {\bf Numerical table} \end{center} $$ \begin{array}{|ccc|} \hline x&A(x)&A(x)\left(\log x\right)^{3/4}\left/x\right.\\ \hline 10^2&47&1.48\\ 10^3&293&1.25\\ 10^4&2\ 204&1.16\\ 10^5&17\ 604&1.100\\ 10^6&148\ 834&1.066\\ 10^7&1\ 297\ 167&1.043\\ 10^8&11\ 562\ 386&1.028\\ .\;.\;.\;.&.\;.\;.\;.\;.\;.&.\;.\;.\\ \infty& &0.937\\ \hline \end{array} $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\refname{References} \begin{thebibliography}{99} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibitem{Bar} E.J. Barbeau, Polynomials, Springer-Verlag, 1989. \bibitem{Bare} E.H. Bareiss, Resultant procedure and the mecchanisation of the Graeffe process, Journal of the ACM, \bf 7 \rm(1960), 346-386. \bibitem{Ben4} F. Ben sa\"id, On a conjecture of Nicolas-S\'ark\"ozy about partitions, to appear in J. Number Theory. \bibitem{Ben} F. Ben sa\"id et J.-L. Nicolas, Sur une extension de la formule de Selberg-Delange, to be published. \bibitem{BenAA} F. Ben sa\"id et J.-L. Nicolas, Sets of parts such that the partition function is even, submitted to Acta Arithmetica. \bibitem{Coh} H. Cohen, High precision computation of Hardy-Littlewood constants, preprint. \bibitem{Gou} X. Gourdon, Th\`ese, http://pauillac.inria.fr/algo/gourdon/thesis /html \bibitem{Gra} C.H. Graeffe, Die Aufl\"osung der h\"oheren numerischen Gleichungen, Zurich, 1837. \bibitem{LN} R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, revised edition, 1994. \bibitem{Mig} M.Mignotte, Math\'ematiques pour le calcul formel, P.U.F., Paris, 1989; english translation: Mathematics for computer algebra, Springer-Verlag, 1992. \bibitem{NRS} J.-L. Nicolas, I.Z. Ruzsa and A. S\'ark\"ozy, On the parity of additive representation functions, J. Number Theory \bf 73 \rm(1998), 292-317. \bibitem{NS} J.-L. Nicolas and A. S\'ark\"ozy, On the parity of generalized partition functions, to appear in the proceedings of the Millennium Conference, Urbana, Illinois, May 2000. \bibitem{Ndeb} J.-L. Nicolas, On the parity of generalised partition functions II, Periodica Mathematica Hungarica, \bf 43 \rm (2001), 177-189. \bibitem{Ono1} K. Ono, Parity of the partition function in arithmetic progressions, J. Reine Angew. Math. \bf 472 \rm (1996), 1-15. \bibitem{Ono2} K. Ono, Distribution of the partition function modulo $m$, Ann. of Math. \bf 151 \rm(2000), 293-307. \bibitem{Ral} A. Ralston and P. Rabinowitz, A first course in numerical analysis, McGraw-Hill, 1978. \end{thebibliography} \end{document}