Wassila Belferdi
email: wassilabelferdi@yahoo.com

Ali Behloul
email: ali.behloul@gmail.com

Protection of digital watermarking based on SVD against false positive detection vulnerability

Keywords: watermarking, blind scheme, singular value decomposition, false positive detection vulnerability, sharing secret principle I

The singular value decomposition (SVD) is drawing the attention as a new transform technique for robust digital watermarking, from the fact that slightly alterations don't affect the image quality. However; several SVD based watermarking algorithms have a serious limitation causing the false positive detection vulnerability. In this paper, we propose watermarking system to counterattack the weakness above mentioned; the proposed technique use the sharing secret principle to calculate secret keys to be embedded in the singular vectors of the watermark as a control parameter, this step invariably ensures that watermark extraction from the watermarked image, using a modified matrix, is not possible, even if it was attacked. Experimental results demonstrate the robustness of our method against attacks.

INTRODUCTION

With the widespread use of Internet to exchange digital media content including images, which can be easy to duplicate, modified and illegally attacked by anyone without deterioration. Day by day the protection of intellectual property gets more difficult, solving this problem; the watermarking is becoming a promising technique to protect data. It is realized by embedding a signal "mark" into a host image that is insensible for the human visual system, after embedding process the watermark should not be removable by unauthorized person and should be robust against intentional and unintentional attacks [START_REF] Terzija | Digital image watermarking using complex wavelet transform[END_REF]- [START_REF] Hameed | Digital image watermarking in the wavelet transform domain[END_REF]. This is done into two phases: watermark embedding and extraction. In general, according to the domain in which the watermark is embedded, the watermarking algorithms can be grouped into spatial and frequency (transform) domain, in spatial domain the watermark is embedded directly to the pixel location [START_REF] Arnold | Techniques and applications of digital watermarking and content protection[END_REF]. On the other hand, for frequency domain the watermark is embedded by transforming the original image into a set of frequency domain [START_REF] Loukhaoukha | On the security of digital watermarking scheme based on SVD and Tiny-GA[END_REF]. Spatial domain methods are less complex as no transform is used, but are not robust against attacks especially to lossy compression [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF]. Transform domain watermarking techniques are robust in comparison to spatial domain methods [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF].

However, the representation of the images in the frequency domain is not necessarily the optimal representation for image. Therefore, other transform representations were explored for watermarking using linear algebra methods such as singular value decomposition (SVD) [START_REF] Loukhaoukha | On the security of digital watermarking scheme based on SVD and Tiny-GA[END_REF].

In recent years, SVD was started use in watermarking as a different transform; it can be used in a wide range of application where data may be organized in a matrix representation [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF], [START_REF] Calagna | A robust watermarking system based on SVD compression[END_REF]. The fact that singular values of an image have a very good stability, that is when small perturbation is added to an image, its singular values don't change significantly [START_REF] Calagna | A robust watermarking system based on SVD compression[END_REF], [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF], so the SVD has attracted attention of researchers for using for watermarking [START_REF] Jain | A reliable SVD based watermarking scheme[END_REF]. But, due to the watermark insertion method, several SVD based watermarking algorithms have a serious limitation; the singular values (SVs) of the watermark are embedded into the SVs of the host image. Then during the detection phase, the watermark is reconstructed using original singular vectors. Another watermark rather than the original can be reconstructed as the embedded watermark; if their singular vectors are used causing the false positive detection vulnerability, so to prevent this attack we propose a method based on sharing secret principle by dividing secret data between the singular vectors of the watermark ensuring that the reconstruction of another watermark from the watermarked image isn't possible. The paper is organized as followed: Section 2 gives an overview of numerous digital watermarking proposed schemes to counterattack the false positive detection vulnerability. In Section 3, we describe the SVD based schemes watermarking algorithms and the false positive detection vulnerability. Section 4 demonstrates the SVD watermarking algorithms using sharing secret principle. Experimental results to validate the proposed watermarking scheme are discussed in Section 5 and conclusions are presented in Section 6.

II. RELATED WORKS

The field of digital watermarking has recently seen numerous novel article covering new techniques. For embedding a watermark in an image, Liu and Tan [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF] have proposed a SVD based watermarking scheme, it was however argued by Zhang and Li [START_REF] Jain | A reliable SVD based watermarking scheme[END_REF], that by taking recourse to the reference matrices of the watermark, the same can be extracted from a possibly distorted watermarked image; this problem has been dealt by Kundur and Hatzinakos [START_REF] Jain | A reliable SVD based watermarking scheme[END_REF] ensuring that the probability of false positive detection remains low.

Recently, a counterfeiting attack has also been proposed. Yavuz and Telatar [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF] proposed a method by applying 3rd level DWT to the cover image, then SVs of the watermark are embedded into SVs of the LL and HL subbands while components of U matrix of the watermark are embedded into LH and HH subbands. In extraction, first the similarity of extracted U matrix is checked with the original one. If it is found similar, the watermark is constructed by using extracted SVs and original U and V matrices of the watermark. While Loukhaoukha [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF] encrypt watermark with the chosen cryptographic function to get the enciphered watermark, in the second method the one-way hash functions is computed for matrices U wc and V wc after appalling the SVD, then hash values are stored in a private key. Then in [START_REF] Loukhaoukha | Optimal image watermarking wlgorithm based on LWT-SVD via multi-objective ant colony optimization[END_REF] the two above mentioned methods are combined to get the algorithm more robust.

Our watermarking scheme does not have the weakness illustrated above since the detector requires the singular vectors of the watermark image. Then, the extracted secret from the possible counterfeit image is compared to the embedded one.

III. SINGLAR VALUE DECOMPOSITION

Recently, singular value decomposition has been used in a variety of applications including images processing. From the viewpoint of linear algebra we can observe that a discrete image is an array of non-negative scalar entries which may be regarded as a matrix.

Let M be an image matrix of size n×m. It can be represented as:

M=USV'=∑  U i V i t . ( 1
)
Where U and V are orthogonal matrices (U t U= I, V t V= I) by size n×n and m×m respectively. Their columns are called respectively left and right singular vectors.

S with size n×m is the diagonal matrix. With r (rank of M matrix) nonzero elements called singular values (SVs) of the matrix M, they are in increasing order meaning that the importance is decreased by going from the first SV to the last one [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF].

If M is an image as in our case, it is important to note that [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF]:

•Singular values correspond to the luminance of the image (image brightness) and corresponding singular vectors specifies the intrinsic geometry properties of the image.

•A slight variation of the singular values don't affect the visual perception of the image (the SVs have a good stability).

•Left singular vectors represent horizontal details while rights singular vectors represent the vertical details of the image [START_REF] Yavuz | Improved SVD-DWT based digital image watermarking against watermark ambiguity[END_REF].

A. False positive detection vulnerability

In [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF] demonstrations that several SVD based schemes watermarking algorithms suffer from the false positive detection vulnerability.

In a blind scheme the SVs of watermark are added to SVs of host image. The matrices of singular vectors U w and V w of the watermark are preserved in private key to be used in extraction phase; watermarked image is composed by using modified singular values matrix and singular vectors (U and V matrices) of host image. In extraction phase, the watermark is restored using U w and V w matrices stored during the embedding phase.

If an attacker use U * and V * matrices of his own watermark in place of reserved ones he can show his own watermark, this is due to the fact only the singular vectors specifies the geometrical property of the image. Moreover, the singular vectors are not inserted at all; this is a serious limitation of the SVD based watermark insertion duo to the watermark insertion method. Fig. 1 show a visual example to the mentioned vulnerability, for more illustration the reader can look at [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF] and [START_REF] Loukhaoukha | On the security of digital watermarking scheme based on SVD and Tiny-GA[END_REF]. IV. PROPOSED METHOD In order to overcome the problem mentioned above with minimal alteration of the scheme proposed by Chandra [START_REF] Loukhaoukha | Tatouage numérique des images dans le domaine des ondelettes basé sur la décomposition en valeurs singulières et l'optimisation multi-objective[END_REF], the idea is to share a secret D between matrices U w , S w and V w of watermark, to avoid that an attacker reconstruct his watermark using their own matrices U * and V * without having the secret D. During the embedding phase, a key is inserted in each matrices U w , S w and V w of watermark, then use the modified S * to reconstruct the watermarked image, those keys are calculated using sharing secret principle.

A. Sharing secret principle

The goal is to divide data D into pieces D i ...D n in such a way that:  Knowledge of any k or more D i makes D easily computable.

 Knowledge of any k-1 or fewer of D i pieces leaves D completely undetermined.

By using a (k, n) threshold scheme with n = 2k-1we get a very robust key management scheme [START_REF] Shamir | How to share a secret[END_REF].

Our scheme is based on polynomial interpolation:

 Given k points in the 2-dimensional plane, with distinct x i 's, there is one and only one polynomial q(x) of degree k -1 such that q(x) =y i for all i. We can assume that the data D is a number to divide it into pieces D i , we pick a random k-1 degree polynomial q(x)=a 0 +a l x+ . . . a k-1 x k-1 in which a 0 =D , and evaluate: D 1 = q(1) ,..., D i = q(i) ,..., D n = q(n).

 Given any subset of k of these D i , we can find the coefficients of q(x) by interpolation, and then evaluate D=q (0).

 Knowledge of just k-1 of these values, on the other hand, does not suffice in order to calculate D.

 To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of integers modulo a prime number p forms a field in which interpolation is possible.

 Given an integer valued data D, we pick a prime p which is bigger than both D and n. The coefficients a 1 ... a k-1 in q(x) are randomly chosen from a uniform distribution over the integers in [0, p-1] and the values D 1 ... D n are computed modulo p.

Some of the useful properties of this (k, n) threshold scheme are:

 The size of each piece does not exceed the size of the original data.

 When k is kept fixed, D i pieces can be dynamically added or deleted without affecting the other D i pieces.

 It is easy to change the D i pieces without changing the original data D all we need is a new polynomial q(x) with the same free term.

During the extraction phase, the matrices U w and V w , saved during the embedding phase, and the matrix S' of the watermarked image, which can be attacked, are used to extract the embedded watermark; if an attacker use their own U * and V * matrices in place of rights matrices the extracting watermark was optical and geometrical similar to the attacker's watermark; at this step the secret D is calculated; if it is different to the inserted one the extraction phase is stopped here.

Let be M and W the image and watermark matrices respectively. I, I' are watermarked image and the attacked one.

B. Embbeding phase

 Apply the SVD to the host image:

M=USV.

(

) 2
 Apply the SVD to the watermark:

W=U w S w V w . (3)
 Calculate keys using sharing secret principle.

 To share the secret D, a key is inserted in each matrices U w , S w and V w .

 Calculate S * using the modified S w :

S * =S+S w . ( 4
)
 Reconstruct the watermarked image I:

I=U w S * V w . ( 5
)
C. Extraction phase  Apply the SVD to the watermarked image maybe attacked:

I'=U'S'V'. (6)
 Calculate S' w :

S' w =(S'-S)/ [START_REF] Loukhaoukha | On the security of digital watermarking scheme based on SVD and Tiny-GA[END_REF]  Retrieve inserted keys from U' w , S' w and V' w .

 Calculate the secret D c using the secret sharing principle and polynomial interpolation:

If D c =D then go to the next step.

Else the extraction phase stops with a probability of an attack of false positive detection.

 Reconstruct the watermark :

W=U w S' w V w . ( 8
)
Embedding and extraction phases are represented in Fig. 2 and Fig. 3.

V. EXPERIMENT RESULTS

In this section we show the robustness of the proposed method against possible attacks. We performed fidelity tests after watermark embedding, whether perceptual distortion occurred to the host image or not. Also we tested the robustness against standard attacks i. e. cropping, Gaussian noise, rotation, resizing and contrast adjustment to the marked image. In experiments, Lina is used as host image; Baboon and Peppers as original and attacker's watermark respectively (Fig. 4 There is no perceptual distortion in the original and watermarked image, which means that the proposed scheme has satisfied the criteria of invisibility. For robustness, as shown in Table I the obtained differences between inserted secret and the calculated one in the case of attacked watermark and the original mark, when our scheme is applied; these experiments give evidence that our watermarking scheme is robust against that kind of attacks. Actually, it depends on the robustness of the SVD against those attacks that's mean that if the SVD based scheme can extract the watermark with a high correlation between the original and the second watermark the secret extraction can continue correctly, as shown in the second and the last lines of Table I the distance between the two differences is still high but the quality of the extracted watermark is low.

To summarize, our scheme is robust against geometrical attacks, including rotation, Gaussian noise, resizing, adjustment contrast and cropping attacks.

But, does the size of watermarked images affect the efficiency of the proposed method?

From the view point that the deference between singular values of an image is decreased, whenever the image size is reduced we applied the following test to check the robustness of our method in this case; results are shown in Table  and Fig. 6. Finally, we show the robustness of our scheme with several images of different sizes, third and fourth columns of Table II show the distance between the original and wrong watermark, the distance is still vast between the inserted secret and the calculated one. With the right watermark the difference |D-D c | is between 5 and 2406, however it is around 188000 with the wrong watermark; this result is meaning that the size of the watermarked image affect the watermark extraction because of the quality of the extracted watermark which decrease going to small images sizes as shown in Table in the same time it doesn't affect the secret extraction from the vast distance obtained.

A. Robustness conditions of the proposed method

In the SVD, the biggest part of energy is concentrated in low frequencies of images, which they are expressed by the nearest coefficients to the left upper corner of the matrix; the watermarking profit this property to insert watermark in low and middle frequencies according to robustness/invisibility compromiser [START_REF] Razafindradina | Robust and blind watermarking in the singular values domain[END_REF]. Experiment shown in Fig. 7 leads as to know where insert the secret according to the above mentioned compromiser.

In our method a secret is inserted at coefficients of the SVD, to evaluate the robustness of the proposed method we have insert a secret in different places of the matrices then we calculate the peak signal to noise ratio (PSNR) between the cover image and the watermarked image and normalized correlation (NC) between the original watermark the extracted one. So from the obtained results we must choice the coefficients that inserted keys must be:

 Different and nonzero values (according the sharing secret principle).

 Inserted at the middle of the coefficients of the SVD, to insure the robustness/invisibility compromiser. We have proposed a robust watermarking scheme, based on SVD using a sharing secret principle. The aim of our solution is to hide the watermark and insure their robustness against the false positive detection vulnerability. Our solution is robust against several attacks. The novelty of our scheme is the use of the sharing secret principle in watermark embedding, that is adaptively chosen according to the local features of the image. This approach makes the solution more robust against the false positive detection vulnerability. The secret is extracted from the attacked image and compared with the inserted one. The experimental results obtained give evidence that our scheme is robust. However, we observe that it is interesting to evaluate the robustness of the watermarking algorithm with different sizes of the watermarked image in conjunction with the previous illustrated attacks.

Our perspective turns around increasing the robustness of our solution using block based SVD scheme.

Figure 1 .

 1 Figure 1. Example of false positive detection vulnerability. (reconstruction of an other watermark from the watermarked image and the attacker watermark)

Figure 2 .

 2 Figure 2. Watermark embedding phase using the proposed method. (the modified Sw is used to reconstruct the watermarked image).

Figure 3 .

 3 Figure 3. Watermark extraction phase using the proposed method. (comparing tow secrets D and Dc to continue the exraction phase or not)

  ); W e is the correct extracted watermark and W e * is the extracted attacker's watermark; |D-D * c | as the difference between the inserted secret and the calculated one in the case of the attack of false positive detection and |D-D c | as the difference in the other case. Results are shown in Table and

Fig. 5 .

 5

Figure 4 .Figure 5 .

 45 Figure 4. Original watermark and attacker's watermark.(used in expirements) Attacks We W*e |D-Dc| |D-D*c|

Figure 6 .

 6 Figure 6. Results of the influence of image size on the robustness of the proposed method. (the distance is wide between the calculated secret and the inserted one with different sizes of images)

Figure 7 .

 7 Figure 7. Robustness conditions of the proposed method.(influence of the insereted secret on the quality of the watermarked image)


Hajime Kaneko
email: kanekoha@math.tsukuba.ac.jp

Thomas Stoll
email: thomas.stoll@univ-lorraine.fr

ON SUBWORDS IN THE BASE-q EXPANSION OF POLYNOMIAL AND EXPONENTIAL FUNCTIONS

Let w be any word over the alphabet {0, 1, . . . , q -1}, and denote by f either a polynomial of degree d ≥ 1 or f : n → m n for a fixed m. Furthermore, denote by e q (w; f (n)) the number of occurrences of w as a subword in the base-q expansion of f (n). We show that lim sup n→∞ e q (w;

where (w) is the length of w and γ(w) ≥ 1 is a constant depending on a property of circular shifts of w. This generalizes work by the second author as well as is related to a generalization of Lagarias of a problem of Erdős.

Introduction

Let q ≥ 2 be an integer and w a non-empty finite word over the alphabet A q := {0, 1, . . . , q -1}. We denote by (w) the length of w which is the number of symbols (or letters) in w. For any integer n ≥ 1, consider the finite base-q expansion of n, n = M i=0 n i q i , where M = M (n) = log q n denotes the position of the most significant digit. We write (n

) q = n M n M -1 • • • n 0
as a shorthand notation and regard this as a word over A q . For convenience, put (0) q := 0. In this paper, we are concerned with the quantity e q (w; n) which denotes the number of (possibly overlapping) occurrences of the word w in the finite base-q expansion of n. For example, for q = 10, w = 202 and n = 20202 we have e 10 (202; 20202) = 2. Note that e q (w; n) ≤ log n log q + 1.

(

) 1
The aim in this paper is to study the quantity e q (w; n) for thin subsequences of the integers. In what follows, we denote by w k the k-th concatenation power of a word w; if k = 0, then w k will denote the empty word. For instance, for the word w = 20 and k = 3 we have w k = 202020. The investigation on the number of occurrences of subwords in digital expansions along special subsequences of integers has undergone some fundamental progress in recent times. A classical point of view, dating back to the work of Gelfond [START_REF] Gelfond | Sur les nombres qui ont des propriétés additives et multiplicatives données[END_REF], is to study the distribution in residue classes. The related sequences are automatic sequences such as, for example, the Thue-Morse sequence or the Rudin-Shapiro sequence. We refer the reader to [START_REF] Drmota | The Thue-Morse sequence along squares is normal[END_REF][START_REF] Hanna | Sur les occurrences des mots dans les nombres premiers[END_REF][START_REF] Mauduit | Prime numbers along Rudin-Shapiro sequences[END_REF][START_REF] Müllner | Automatic sequences fulfill the Sarnak conjecture[END_REF][START_REF] Stoll | On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence[END_REF] for an up-to-date list of the related work.

A second and different problem is to investigate the number of occurrences of digital blocks in these rarefied sequences. We will consider this problem along polynomial and exponential subsequences in the present paper. We will show that for any fixed w there are terms in these rarefied sequences whose base-q expansion contains not too few occurrences of w as subwords. For that purpose we will establish lower bounds on the maximal order of magnitude of the associated counting function.

We denote the set of nonnegative integers (resp. positive integers) by N (resp. Z + ) and use the standard Landau resp. Vinogradov notation f = O(g) resp. f g to indicate that |f | ≤ C|g| for some absolute constant C > 0. As common, we denote a possible dependence on the parameters in the index of the symbols.

For a better understanding of the flavour of our results, let us first give two examples in the case of a polynomial rarification.

First, consider w = 0 l (l fixed) which is the l-th concatenation power of the single letter 0 and let f (X) ∈ Z[X] be any arbitrary but fixed polynomial of degree d ≥ 1 with f (N) ⊂ N. Since by [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF],

e q (w; f (n)) ≤ log f (n) log q + 1
for all non-empty words w and sufficiently large n, we have lim sup

n→∞ e q (w ; f (n)) log n ≤ d log q . ( 2
)
On the other hand, by choosing a positive integer a such that the coefficients of f (X + a) are all positive, we have lim sup n→∞ e q (w ;

f (n)) log n ≥ lim sup L→∞ e q (w ; f (q L + a)) log(q L + a) ≥ d log q . ( 3
)
This is due to fact that in the base-q expansion of f (q L + a) the d blocks of 0's between consecutive powers of q are each of length L + O q,f (1) as L → ∞. The two inequalities (2) and (3) lead to lim sup n→∞ e q (w ;

f (n)) log n = d log q . ( 4
)
As a second example, on the other end of the spectrum, let w = (q -1) l be the l-th concatenation power of the single letter q -1. Theorem 1 in [START_REF] Stoll | On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence[END_REF] states that there exists N 0 (q, f, l) > 1 such that for all N ≥ N 0 (q, f, l) there is an n with e q (w ; f (n)) = N. From the method of the proof, it follows that lim sup n→∞ e q (w ;

f (n)) log n ≥ 1 log q . ( 5
)
In fact, in the proof the author generates one block of consecutive q -1's, hence also losing the factor d with respect to the previous result.

Our first result gives a result for general w in the spirit of ( 5) and deals with a question posed in [START_REF] Stoll | On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence[END_REF]. Theorem 1. Let q ≥ 2 be a positive integer and let w be a finite word in the alphabet A q = {0, 1, . . . , q -1} with length (w

) ≥ 1. Let f (X) ∈ Z[X] be a polynomial of degree d ≥ 1 with f (N) ⊂ N. Then lim sup n→∞ e q (w; f (n)) log n ≥ γ(w) (w) log q ,
where γ(w) = γ (w)-1 and γ (w) ≥ 2 is the number of circular shift occurrences of w in w 2 .

Note that 1 ≤ γ(w) ≤ (w) for all non-empty words w. For example, γ(2020) = 2, γ(0 l ) = γ((q -1) l ) = l. Unfortunately, our method of proof does not allow to get the degree d as a multiplicative factor in the lower bound (compare with (3)).

We conjecture that (4) holds true for any w, however, this seems to be a very difficult question.

Conjecture 1. Let f (X) ∈ Z[X] be a polynomial of degree d ≥ 1 with f (N) ⊂ N.
Let w be a word in the alphabet A q = {0, 1, . . . , q -1} with length (w) ≥ 1 and denote by e q (w; f (n)) the number of (possibly overlapping) occurrences of the word w in the finite base-q expansion of f (n). Then

lim sup n→∞ e q (w; f (n)) log n = d log q .
Our second result concerns exponential functions. A famous (still open) problem by Erdős says that for all sufficiently large n the ternary expansion of 2 n always contains the digit 2. We refer to the article of Lagarias [START_REF] Lagarias | Ternary expansions of powers of 2[END_REF] and to [START_REF] Dupuy | Bits of 3 n in binary, Wieferich primes and a conjecture of Erdős[END_REF] for recent and related results. Lagarias [8, Conjecture 1.12] generalized Erdős' conjecture: For all multiplicatively independent positive integers m and q the base-q expansion of the integers m n , n = 1, 2 . . . contain any given word w in its base-q expansion for all sufficiently large n ≥ n 0 (w). While Theorem 2 does not provide an answer to this conjecture it gives a quantitative lower bound along a subsequence of integers and therefore (up to a constant factor) the correct maximal order of magnitude.

Theorem 2. Let p ≥ 2 be a prime number and let w be a finite word in the alphabet

A p = {0, 1, . . . , p -1} with length (w) ≥ 1. Let f (x) = m x for an integer m ≥ 2, m not a power of p. Then lim sup n→∞ e p (w; m n ) log n ≥ γ(w) (w) log p ,
where γ(w) = γ (w)-1 and γ (w) ≥ 2 is the number of circular shift occurrences of w in w 2 .

In Section 2 we provide a proof of Theorem 1 and Section 3 is devoted to a proof of Theorem 2. Both proofs are based on Hensel's lifting lemma. For a prime number p we use Z p for the ring of p-adic integers and Q p for the field of p-adic numbers; we denote by v p (u) the p-adic order of u ∈ Z p .

Proof of Theorem 1

In what follows, we suppose that w = 0 l since we have a better result by (4) in the case of a block consisting of 0's only. We start with an important auxiliary result.

Lemma 1. Let f (X) ∈ Z[X] be a polynomial of degree d ≥ 1 with f (N) ⊂ N.
Denote by a 0 a nonnegative integer satisfying f (a 0 ) = 0. Let w be a word in the alphabet A q = {0, 1, . . . , q -1} that we write

w = 0 k w k+1 • • • w l , k + 1 ≤ l
with w k+1 = 0, where all of the w i , i = k + 1, . . . , l, are of length 1 (letters).

For any positive integers c and L let L be the length of the word w L 0 c (f (a 0 )) q .

Then there exists c = c(q, f ) > 0 only depending on q and f , such that for any positive integer L there is a nonnegative integer N < q L with

(f (N )) q = vw k+1 • • • w l w L-1 0 c (f (a 0 )) q ,
where v is some finite (or the empty) word over A q = {0, 1, . . . , q -1}.

Proof. Let q := p e1 1 • • • p et t , where p 1 , . . . , p t are distinct prime factors of q and e 1 , . . . , e t are positive integers. Let b q,L be a nonnegative integer whose base-q expansion is denoted as

(b q,L ) q = w k+1 • • • w l w L-1 0 c (f (a 0 )) q ,
for some c that we will determine later.

Let L be the length of the word w L 0 c (f (a 0 )) q . For any i = 1, . . . , t, consider the p i -adic order of an integer m by v pi (m). If c is sufficiently large depending only on q and f (X), then we see for any i = 1, . . . , t that

v pi (f (a 0 ) -b q,L ) > 2v pi (f (a 0 )) by f (a 0 ) = 0. Putting g(X) := f (X) -b q,L , we get v pi (g(a 0 )) > 2v pi (f (a 0 )) = 2v pi (g (a 0 )).
By Hensel's lifting lemma [START_REF] Lang | Algebraic Number Theory[END_REF] there exists a p i -adic integer ξ i ∈ Z pi such that f (ξ i ) = b q,L . Thus, for any i = 1, . . . , t, there exists an integer

N i ≤ p L ei i such that f (N i ) ≡ b q,L (mod p L ei i ).
By the Chinese remainder theorem, there is an integer N with

0 ≤ N < p L e1 1 • • • p L et t = q L (6)
and

N ≡ N i (mod p L ei i )
for any i = 1, . . . , t. Consequently, we obtain f (N ) ≡ b q,L (mod q L ), which implies the lemma.

Note that the statement of the lemma also implies an upper bound on the length of the prefix v.

We are now ready to prove Theorem 1.

Proof of Theorem 1.

In what follows, we use the integer N constructed in the proof of Lemma 1 (note that N < q L , see ( 6)). For any positive integer L, we see by Lemma 1 that e q (w; f (N )) ≥ γ(w)(L -2). ( 7)

By [START_REF] Kaneko | Hensel's lemma for general continuous functions[END_REF] and the definition of L , we get

N < q L ≤ q lL+c , (8)
where c = c (q, f ) is a constant depending only on q and f (X). Thus, we obtain from ( 7) and ( 8) that

1 l log q - c l log N ≤ L log N ≤ 2 log N + e q (w; f (N )) γ(w) log N .
Noting that N tends to infinity as L tends to infinity (by w = 0 l ), we deduce the theorem by the inequality above. This concludes the proof of Theorem 1.

Proof of Theorem 2

For the proof of Theorem 2, we first introduce a generalization of Hensel's lemma and define the notation which we use throughout this section. Let p be a prime number. For any positive integer m 1 with m 1 ≡ 1 (mod p), we set m 1 = 1+ap e , where a, e are positive integers with p a. Put g(u) := (1+ap e ) u for any u ∈ Z p . Let again v p (u) be the p-adic order of u ∈ Z p . It is known that for any u, u ∈ Z p with v p (u -u ) ≥ N and N ∈ N, we have

v p g(u) -g(u ) ≥ N + 1 (9)
(see [START_REF] Koblitz | p-adic Numbers, p-adic Analysis, and Zeta-Functions, 2nd edition[END_REF]Chapter 2,p.26]).

Let F be a function from Z p to Z p and let u be a fixed element of Z p . We call F differentiable modulo p s at u with order N , where s ∈ Z + and N ∈ N, if there exists ∂ s F (u) ∈ Q p satisfying, for any integer k > N and h ∈ Z p ,

F (u + p k h) ≡ F (u) + p k h∂ s F (u) (mod p k+s ). ( 10
)
Note that if we add a constant term to F , then both the differentiability of F and the value ∂ s F (u) are not changed.

In the following proposition we generalize the second statement of Corollary 2.6 in [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF]. This is needed in order to consider the case where the derivative is not a p-adic unit. We investigated this concept for general continuous functions that are not necessarily differentiable in [START_REF] Kaneko | Hensel's lemma for general continuous functions[END_REF].

Proposition 1. Let F be a function from Z p to Z p . Let j, n, s, N be nonnegative integers with j + N < n and j < s and let u ∈ Z p . Assume that

v p F (u) ≥ n. (11)
Moreover, suppose for any x ∈ Z p with x ≡ u (mod p n-j ) that F is differentiable modulo p s at x with order N and that

v p ∂ s F (x) = j. (12)
Then there exists a ξ ∈ Z p satisfying F (ξ) = 0 and ξ ≡ u (mod p n-j ).

Proof. We construct ξ ∈ Z p satisfying the conditions of Proposition 1, using the Newton method. It suffices to show that there exists a u 1 ∈ Z p satisfying

v p F (u 1 ) ≥ n + 1 (13)
and

u 1 ≡ u (mod p n-j ). (14)
In fact, u 1 will then satisfy [START_REF] Müllner | Automatic sequences fulfill the Sarnak conjecture[END_REF], the assumption on the differentiability, and ( 12) with new nonnegative integers j 1 = j, n 1 = n + 1, s 1 = s, and

N 1 = N because if x ∈ Z p satisfies x ≡ u 1 (mod p n1-j1
), then x ≡ u (mod p n-j ).

Let i be an integer with 0 ≤ i ≤ p -1. Noting that n -j > N and n -j + s ≥ n + 1, we see by [START_REF] Mauduit | Prime numbers along Rudin-Shapiro sequences[END_REF] that

F u + p n-j • i ≡ F (u) + p n-j • i∂ s F (u) (mod p n+1 ). Using v p p n-j ∂ s F (u) = n ≤ v p F (u) ,
we find i satisfying

F (u + p n-j • i) ≡ 0 (mod p n+1 ).
Putting u 1 := u + p n-j • i, we obtain (13) and ( 14).

We now prove the differentiability of the function g(u) = (1 + ap e ) u , where a and e are positive integers with p a. Proposition 2. Let g(u) = (1 + ap e ) u , where a, e are positive integers with p a.

1. Suppose that e ≥ 2 or p ≥ 3. Then, for any u ∈ Z p , we have that g is differentiable modulo p e+1 at u with order 0. Moreover,

∂ e+1 g(u) = ap e .

2.

Assume that e = 1 and p = 2. Let 1 + a • 2 t := (1 + 2a) 2 , where a and t are integers with 2 a and t ≥ 3. Then g is differentiable modulo 2 t at u with order 0. Moreover,

∂ t g(u) = a 2 t-1 .
For the proof of Proposition 2, we need the following auxiliary result.

(u + hp k ) = g(u)(1 + ap e ) hp k ≡ g(u)(1 + ahp e+k ) (mod p k+e+1 ) ≡ g(u) + hp k • ap e (mod p k+e+1 )
by g(u) ≡ 1 (mod p), which implies the first statement.

Next, suppose that e = 1 and p = 2. In the same way as above, using Lemma 2 again, we see by k -1 ≥ 0 that

g(u + 2 k • h) = g(u)(1 + a • 2 t ) h•2 k-1 ≡ g(u) + (h • 2 k ) • (a • 2 t-1 ) (mod 2 k+t ),
which implies the second statement.

We are now ready to give a proof of Theorem 2.

Proof of Theorem 2. We may assume that m and p are coprime. In fact, if m is not coprime to p, then putting m =: m p s , where s = v p (m) and m ≥ 2, we have e p (w; m n ) ≥ e p (w; m n ).

Combining ( 18) and (19), we deduce Theorem 2 by letting L tend to infinity.

Put m p- 1 =: 1 + 1 i=0v

 111 ap e and g(u) := (1 + ap e ) u , where a and e are positive integers with p a and u ∈ Z p . If p = 2 and e = 1, then we define a and t as in Proposition 2.For any finite wordv = v d-1 v d-2 • • • v 0 on the alphabet A p , we put ϕ p (v) := di p i .Moreover, for any positive integer L, letϕ p (w L 0 c 1) =: b p,L ,for some c that we will determine later. Put F (u) := g(u)-b p,L for u ∈ Z p . We apply Proposition 1 with u = 0, N = 0,j = e if e ≥ 2 or p ≥ 3, t -1 if e = 1 and p = 2, s = j + 1, n = j + 1 and put c := n -1. Then we see v p F (0) = v p (1 -b p,L ) ≥ n,which implies[START_REF] Müllner | Automatic sequences fulfill the Sarnak conjecture[END_REF]. Moreover, the assumption on the differentiability and[START_REF] Stoll | On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence[END_REF] in Proposition 1 are satisfied by Proposition 2.Thus, Proposition 1 implies that there exists ξ ∈ Z p satisfying g(ξ) = b p,L . Let L be the length of the word w L 0 c 1. Then we haveL = lL + c + 1.Let N be an integer with p L ≤ N < 2p L and N ≡ ξ (mod p L ).Using[START_REF] Lang | Algebraic Number Theory[END_REF], we getm (p-1)N = g(N ) ≡ g(ξ) = b p,L (mod p L )(17)Putting N = (p -1)N , we obtain by (17) and m N > p L that e p (w; m N ) ≥ γ(w)(L -1) (18) and that log N ≤ log 2(p -1) + L log p = log 2(p -1) + (c + 1) log p + lL log p.

  Lemma 2. Assume that e ≥ 2 or p ≥ 3. Let k be a nonnegative integer and h ∈ Z p . Then we have(1 + ap e ) hp k ≡ 1 + ahp k+e (mod p k+e+1 ).Proof. We may assume that h is a nonnegative integer because N is dense in Z p . Moreover, it suffices to show (15) in the case where h is not divisible by p.In fact, assume that (15) holds for any h ∈ N not divisible by p. Then, for any nonnegative integer h = h p s , where s = v p (h) ≥ 1, we see(1 + ap e ) hp k = (1 + ap e ) h p k+s ≡ 1 ≡ 1 + ahp k+e (mod p k+e+1 ), from (16) by considering the binomial expansion of (1 + ap k+e ) h .Proof of Proposition 2. Let k be any positive integer and u, h ∈ Z p . First, we assume that e ≥ 2 or p ≥ 3. Using Lemma 2, we get g

	which implies (15).
	First, we show (15) in in the case of h = 1, namely,
	(1 + ap e ) p k	≡ 1 + ap k+e (mod p k+e+1 ).	(16)
	If k = 0, then (16) is trivial. If k ≥ 1, then the inductive hypothesis implies
	that
	(1 + ap
			(15)

e ) p k-1 = 1 + ap e+k-1 + cp e+k for some integer c, and so

(1 + ap e ) p k = (1 + ap e+k-1 + cp e+k ) p ≡ (1 + ap e+k-1 ) p (mod p k+e+1 ). Since (1 + ap e+k-1 ) p = 1 + ap e+k + p j=2 p j (ap e+k-1 ) j ,

we deduce (16), using e + k < p(e + k -1) by k ≥ 1, and e ≥ 2 or p ≥ 3. Finally, if h ≥ 0 is a general integer not divisible by p, then (15) follows

The first author is supported by JSPS KAKENHI Grant Number 15K17505.

The second author acknowledges the support of the bilateral project ANR-FWF (France-Austria) called MUDERA (Multiplicativity, Determinism, and Randomness), ANR-14-CE34-0009.

Acknowledgement

We would like to thank the reviewers for helpful remarks that helped to improve the presentation of our results.


Hajime Kaneko
email: kanekoha@math.tsukuba.ac.jp

Thomas Stoll
email: thomas.stoll@univ-lorraine.fr

HENSEL'S LEMMA FOR GENERAL CONTINUOUS FUNCTIONS

Keywords: 2010 Mathematics Subject Classification. 11D88 (primary), and 11S85 (secondary) Hensel's lifting lemma, van der Put series, p-adic analysis

 who showed the validity of Hensel's lemma for 1-and for p α -Lipschitz functions. For the statement and the proof, we introduce a suitable generalization of the original van der Put series. We use the concept of approximability of continuous functions to give numerical examples.

Introduction

Denote by N (resp. Z + ) the set of nonnegative integers (resp. positive integers). Let p be a prime number and Z p the ring of p-adic integers. We denote v p (u) (resp. |u| p ) the p-adic order (resp. the p-adic absolute value) of u ∈ Z p normalized with v p (p) = 1 (resp. |p| p = p -1 ). We first recall Hensel's lifting lemma. Let Q(X) ∈ Z p [X]\Z p and u ∈ Z p . Assume that

v p (Q(u)) > 2v p (Q (u)).
Then there exists a unique ξ ∈ Z p satisfying v p (ξ -u) > v p (Q (u)) and Q(u) = 0. Axelsson and Khrennikov [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF] generalized Hensel's lemma to 1-Lipschitz functions, namely to functions f : Z p → Z p which satisfy |f (x) -f (y)| p ≤ |x -y| p for any x, y ∈ Z p (from this, they derived also a generalization for p α -Lipschitz functions, α ≥ 1). For the statement and the proof of their generalization, they used van der Put series applied to this class of functions. Van der Put series date back to the work of M. van der Put [START_REF] Van Der Put | Algèbres de fonctions continues p-adiques. I[END_REF][START_REF] Van Der Put | Algèbres de fonctions continues p-adiques. II[END_REF] and have shown to be very fruitful in p-adic analysis, dynamical systems and ergodic theory (see [START_REF] Schikhof | Ultrametric Calculus. An Introduction to p-adic Analysis[END_REF]) as well as in various applications in cryptography, computer science and numerical analysis (see [START_REF] Anashin | Applied Algebraic Dynamics[END_REF] for a detailed account on the various applications). For the application to dynamical systems it is natural to investigate the minimal conditions on the functions that allow such series expansions.

Axelsson and Khrennikov [3, p.224, Remark 2.5] asked for a generalization of Hensel's lemma to any continuous function f : Z p → Z p which would lead to an extension to their result. In this article, we provide such a generalization of Hensel's lemma to any continuous function, introducing the notion of generalized van der Put series and approximability of continuous functions. We consider the existence of the zeros of continuous functions and discuss uniqueness under certain conditions.

We first recall Theorem 2.4 of [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF] (notation and statements are slightly modified for convenience to generalization; cf. [START_REF] Anashin | T -functions revisited: new criteria for bijectivity/transitivity[END_REF]). For a positive integer m, we denote its base-p expansion by

m = m 0 + m 1 p + • • • + m k p k , (1.1)
where k = k(m) = log p m and log p m = log m/ log p. In other words, k is a unique positive integer with

p k ≤ m < p 1+k , (1.2) and m 0 , m 1 , . . . , m k ∈ {0, 1, . . . , p -1}, m k = 0. For convenience, if m = 0, put k = k(0) = log p 0 := 0. (1.3) Set χ(m, x) = 1 if |x -m| p ≤ p -1-k , 0 otherwise
for any x ∈ Z p . Let f : Z p → Z p be any continuous function. Then there exists a unique sequence B(f ; m) (m = 0, 1, . . .) such that

f (x) = ∞ m=0 B(f ; m)χ(m; x) (1.4)
for any x ∈ Z p , where (1.4) is called the van der Put series of f . Moreover, B(f ; m) satisfies

B(f ; m) = f (m) if m < p, f (m) -f (m -m k p k ) otherwise.
Anashin, Khrennikov and Yurova [2, Theorem 5] showed that f is 1-Lipschitz if and only if

v p (B(f ; m)) ≥ log p m (1.5)
for any nonnegative integers m. Thus, we see if

f is 1-Lipschitz, then b(f ; m) := p -log p m B(f ; m) ∈ Z p .
We are now ready to state the main result of [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF]. (The condition m ≥ R, appearing in the second assumption in [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF]Theorem 2.4], is a typo and has to be omitted.) THEOREM 1.1 (Theorem 2.4 in [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF]). Let f : Z p → Z p be a 1-Lipschitz function. Let R 0 be a positive integer and u an integer with 0 ≤ u < p R0 and f (u) ≡ 0 (mod p R0 ).

For any nonnegative integers m, R with

m < p R , m ≡ u (mod p R0 ), R ≥ R 0 , assume that {b(f ; m + i • p R ) mod p | i = 1, 2, . . . , p -1} = {j mod p | j = 1, 2, . . . , p -1}.
Then there exists a unique ξ ∈ Z p satisfying f (ξ) = 0 and ξ ≡ u (mod p R0 ).

The fact that b(f ; m) ∈ Z p , which does not generally hold for continuous functions, is essential for the proof of Theorem 1.1. Thus, it is necessary to generalize van der Put series.

The structure of the paper is as follows. In Section 2 we define generalized van der Put series by introducing a strictly increasing integer-valued function Φ. This function corresponds to the concept of the modulus of continuity in the case of realvalued continuous functions. We then use this generalization in Section 3 to classify general continuous functions and to state and prove our main result (Theorem 3.2). In Section 4 we generalize the notion of derivative and approximability to this context. Along our way, we illustrate our results by some concrete examples.

Generalized van der Put series

This section is devoted to our generalization of van der Put series. Let Φ : N → N be a strictly increasing function. In the case of Φ = Id, the identity function on N, we recover the original van der Put series. To begin with, for any given p-adic integer

x = ∞ i=0 x i p i (2.1)
with x i ∈ {0, 1, . . . , p -1} we split its terms according to Φ, namely,

x = ∞ j=0 Φ(j) i=Φ(-1+j)+1 x i p i , (2.2)
where we denote Φ(-1) := -1 for convenience. For any nonnegative integer m put τ (m) = τ (Φ; m) := min h ∈ N m < p 1+Φ(h) and, for any x ∈ Z p , χ(Φ, m; x) := 1 if |x -m| p ≤ p -1-Φ(τ (m)) , 0 otherwise.

Then we see τ (Id; m) = k by (1.2), (1.3), and so χ(Id, m; x) = χ(m; x) for any x ∈ Z p by Φ(τ (m)) = k. Let m be a nonnegative integer with τ (m) ≥ 1, namely, m ≥ p 1+Φ(0) . Denote the base-p expansion of m by (1.1). Set

M (m) = M (Φ; m) := Φ(τ (m)) i=Φ(-1+τ (m))+1 m i p i . Note that M (Id; m) = m k p k by Φ(τ (m)) = Φ(-1 + τ (m)) + 1 = k. PROPOSITION 2.1. For any continuous function f : Z p → Z p there exists a unique sequence B(m) = B(Φ, f ; m) (m = 0, 1, . . .) such that f (x) = ∞ m=0 B(Φ, f ; m)χ(Φ, m; x) (2.3) for any x ∈ Z p . Moreover, B(Φ, f ; m) satisfies B(Φ, f ; m) = f (m) if m < p 1+Φ(0) , f (m) -f (m -M (m)) otherwise. (2.4)
We note that B(Id, f ; m) = B(f ; m) for any nonnegative integer m.

Proof of Proposition 2.1. We first show that the sequence B(Φ, f ; m) (m = 0, 1, . . .) defined inductively by (2.4) satisfies (2.3) (existence). For x ∈ Z p set

F (x) := ∞ m=0 B(Φ, f ; m)χ(Φ, m; x). (2.5)
The convergence of the right-hand side of (2.5) follows from the uniform continuity of f and lim

m→∞ |M (m)| p = 0
by the assumption that Φ is strictly increasing. For any x ∈ Z p with (2.1) and any nonnegative integer j, set

x(j) := Φ(j) i=0 x i p i . (2.6) Observe that F (x) = ∞ j=0 m∈N,τ (m)=j B(Φ, f ; m)χ(Φ, m; x).
Let again j be a nonnegative integer. Then, for any m ∈ N with τ (m) = j, we have that

χ(Φ, m; x) = 1 if and only if τ (x(j)) = j and m = x(j). (2.7)
It is easily seen that τ (x(j)) = j if and only if j = 0 or x(j) > x(j -1) because

x(j) = x(j -1) + Φ(j) i=Φ(j-1)+1 x i p i for j > 0. Letting J(x) := {0} ∪ {j ∈ Z + | x(j) > x(j -1)},
we get by (2.4) that, for any j ∈ J(x)\{0},

B(Φ, f ; x(j)) = f (x(j)) -f (x(j -1))
and that

F (x) = j∈J(x) B(Φ, f ; x(j)) = f (x(0)) + j∈J(x)\{0} f (x(j)) -f (x(j -1)) .
Moreover, if j ∈ N\J(x), then we have f (x(j)) -f (x(j -1)) = 0. Thus, we see

F (x) = f (x(0)) + ∞ j=1 f (x(j)) -f (x(j -1)) = f (x) by lim j→∞ x(j) = x.
Next, we prove that if B(m) (m = 0, 1, . . .) is a sequence satisfying (2.3) for any x ∈ Z p , then (2.4) holds by induction on τ (m) (uniqueness). We use the notation x(j)(j = 0, 1, . . .) and J(x) in the case where x = m. First, we consider the case of τ (m) = 0, namely, m < p 1+Φ(0) . Using (2.3) and (2.7), we get

f (m) = B(m(0)) = B(m)
by τ (m(j)) = 0 for any j ∈ N, which implies (2.4). We now assume that (2.4) holds for any nonnegative integer m with τ (m) ≤ j for a fixed integer j ≥ 0. Let m be a nonnegative integer with τ (m) = j + 1. Then we see J(m) ⊂ [0, j + 1]. Using again (2.3) and (2.7), we get

f (m) = l∈J(m) B(m(l)). (2.8) Put J(m) := {0 = j 0 < • • • < j κ-1 < j κ },
where κ ≥ 1 and m(j κ ) = m and m(j κ-1 ) = m -M (m). Hence, we obtain by (2.8) and the inductive hypothesis that

f (m) = B(m(0)) +   l∈J(m),1≤l≤jκ-1 B(m(l))   + B(m(j κ )) = f (m(0)) +   l∈J(m),1≤l≤jκ-1 f (m(l)) -f (m(l -1))   + B(m) = f (m(0)) +   1≤l≤jκ-1 f (m(l)) -f (m(l -1))   + B(m) = f (m(j κ-1 )) + B(m) = f (m -M (m)) + B(m),
which implies (2.4). Therefore, we proved the proposition.

Hensel's lemma for continuous functions

In what follows, we use notation (2.1) and (2.2) for a p-adic integer x. Let Φ : N → N be a strictly increasing function as used in the previous section. In order to state Hensel's lemma for continuous functions, we define a certain class of continuous functions based on the use of Φ.

Let f : Z p → Z p be a continuous function and n a positive integer. Since f is uniformly continuous on Z p , there exists a nonnegative integer l such that, for any

x, y ∈ Z p , if |x -y| p ≤ p -l then |f (x) -f (y)| p ≤ p -n . We denote the minimal value of such an l by ψ(f ; n). Note that ψ(f ; n) (n = 1, 2, . . .) is non-decreasing.
Let F(Φ) be the class of continuous functions f :

Z p → Z p satisfying ψ(f ; n) ≤ 1 + Φ(n -1)
for any positive integer n, namely, for any x, y

∈ Z p , if |x -y| p ≤ p -1-Φ(n-1) , then |f (x) -f (y)| p ≤ p -n . (3.1) Note that |x -y| p ≤ p -1-Φ(n-1) is equivalent to Φ(n-1) i=0 x i p i = Φ(n-1) i=0 y i p i .
We see for any continuous f that f ∈ F(Id) if and only if f is 1-Lipschitz.

For any continuous function f , we see that there exists a strictly increasing function Φ such that f ∈ F(Φ), defining Φ as follows:

Φ(0) := max{0, -1 + ψ(f ; 1)}, Φ(n) := max{1 + Φ(n -1), -1 + ψ(f ; n + 1)}
for any positive integer n.

We now generalize (1.5) as follows: Conversely, we assume (3.2). Let n be a positive integer and let x, y ∈ Z p with v p (x -y) ≥ 1 + Φ(n -1), namely,

Φ(n-1) i=0 x i p i = Φ(n-1) i=0 y i p i .
Observe for any integer m with 0 ≤ m < p 1+Φ(n-1) that χ(m; x) = χ(m; y) because χ(m; x) (resp. χ(m; y)) depends only on the first Φ(n -1)-th digits of x (resp. y) by τ (m) ≤ n -1. Thus, Proposition 2.1 implies that

f (x) -f (y) = m≥p 1+Φ(n-1) B(m) χ(m; x) -χ(m; y) .
For any integer m with m ≥ p 1+Φ(n-1) , we get by (3.2) that x i p i .

v p (B(m)) ≥ τ (m) ≥ n,
We now introduce a generalization of Theorem 1.1 for continuous functions. THEOREM 3.2. Let Φ : N → N be a strictly increasing function and let f ∈ F(Φ). Let h, n 0 and u be nonnegative integers with u < p 1+Φ(n0) and f (u) ≡ 0 (mod p 1+h+n0 ). (3.4) Suppose that there exists a sequence (S(n)) n≥n0 of sets of nonnegative integers with

S(n) ⊂ 0, p Φ(n+1)-Φ(n) , Card S(n) = p -1,
where Card denotes the cardinality, satisfying the following: For any nonnegative integers n, m with REMARK 2. As we will see in Section 4, if f is differentiable modulo p s at u, then h corresponds to the p-adic order of the derivative of f . If Φ = Id and h = 0 then 1 + n 0 = 1 + Φ(n 0 ) which is the value of R 0 in Theorem 1.1. Thus, Theorem 3.2 with Φ = Id and h = 0 implies Theorem 1.1. REMARK 3. Note that (3.9) always holds if h = 0. REMARK 4. A sequence (S(n)) n≥n0 satisfying the assumptions of Theorem 3.2 is not generally unique. In Example 3.1, we consider the case where (3.9) holds. We give two solutions ξ satisfying (3.6) and (3.7), by changing (S(n)) n≥n0 . It would be an interesting question to try to prove the uniqueness of ξ without assuming (3.9).

n ≥ n 0 , m < p 1+Φ(n) , m ≡ u (mod p 1+Φ(n0) ), we have b Φ, f ; m + ip 1+Φ(n) mod p h+1 i ∈ S(n) = ip h mod p h+1 i = 1, 2, . . . , p -1 .
Proof of Theorem 3.2. First, we prove the existence of such ξ by using Newton's method. We show by induction on j that there exists a unique sequence (u j ) j≥n0 of integers with

u n0 = u ∈ [0, p 1+Φ(n0) ) ∩ Z (3.10)
satisfying the following:

(1) For all j ≥ n 0 , f (u j ) ≡ 0 (mod p 1+h+j ). (3.11) (2) If j ≥ 1 + n 0 , then there exists i ∈ {0} ∪ S(j -1) such that

u j = u j-1 + ip 1+Φ(j-1) , 0 ≤ u j < p 1+Φ(j) . (3.12)
The case of j = n 0 follows from (3.4). We assume that there exist unique integers u n0 , u 1+n0 , . . . , u l for l ≥ n 0 satisfying (3.10), (3.11) and (3.12) for j = n 0 , 1 + n 0 , . . . , l. Let i ∈ S(l). We see by p 1+Φ(l) ≤ ip 1+Φ(l) ≤ -p 1+Φ(l) + p 1+Φ(l+1) that

τ u l + ip 1+Φ(l) = l + 1 and that M u l + ip 1+Φ(l) = ip 1+Φ(l) .
Thus, using (3.3) and (2.4) with m = u l + ip 1+Φ(l) , we get

f u l + ip 1+Φ(l) = f (u l ) + p l+1 b u l + ip 1+Φ(l) . (3.13) Since u l ≡ u n0 = u (mod p 1+Φ(n0)
) by (3.12) with j = n 0 , 1 + n 0 , . . . , l, we can apply (3.5) with n = l, m = u l . Since f (u l ) ≡ 0 mod p l+1+h , selecting suitable i ∈ {0} ∪ S(l), we obtain that

u l+1 := u l + ip 1+Φ(l) (< p 1+Φ(l+1) )
is a unique integer satisfying (3.11) and (3.12) with j = l + 1. Putting ξ := lim j→∞ u j we showed the existence of ξ. In fact, if n ≥ n 0 , then

Φ(1+n) j=1+Φ(n) ξ j p j = u n+1 -u n = ip 1+Φ(n) .
Thus, (3.8) holds with ρ(ξ; n + 1) = i.

We now prove the uniqueness of ξ. We see that the sequence (ξ(j)) j≥n0 , defined by (2.6) for x = ξ, satisfies (3.12) by (3.8) :

ξ(j) = ξ(j -1) + ρ(ξ; j)p 1+Φ(j-1) , j ≥ 1 + n 0 ,
where ρ(ξ; j) ∈ {0} ∪ S(j -1). Moreover, (3.10) holds by 0 ≤ ξ(n 0 ) < p 1+Φ(n0) and (3.7). In the same way as the proof of Proposition 3.1, we can show for any j ≥ n 0 that

f (ξ) -f (ξ(j)) = m≥p 1+Φ(j) B(m) χ(m; ξ) -χ(m; ξ(j)) = m≥p 1+Φ(j) b(m)p τ (m) χ(m; ξ) -χ(m; ξ(j)) .
We fix an integer m with m ≥ p 1+Φ(j) (≥ p 1+Φ(n0) ). Then we have χ(m; ξ(j)) = 0 by τ (m) ≥ j + 1 > j ≥ τ (ξ(j)). Moreover, χ(m; ξ) = 1 if and only if m = ξ(j ) for some j ≥ j + 1. In particular, if χ(m; ξ) = 1, then we have m ≡ u mod p 1+Φ(n0) .

For any integer m with m ≥ p 1+Φ(j) and m ≡ u mod p 1+Φ(n0) , we see by (3.9)

that v p (b(m)p τ (m) ) ≥ h + τ (m) ≥ 1 + h + j.
Thus, we get by (3.6) that

f (ξ(j)) ≡ f (ξ) = 0 (mod p 1+h+j ),
which implies (3.11). By the uniqueness of (u j ) j≥n0 , we see ξ(j) = u j for all j ≥ n 0 . This concludes the proof of the theorem.

Example 3.1. Let a = ∞ i=0 a i p i ∈ Z p be fixed and f : Z p → Z p be defined by

f (x) = a + ∞ j=0 x 2j p j , where x = ∞ i=0 x i p i . Let Φ(n) := 2n + 1 for any nonnegative integer n. Then we have f ∈ F(Φ). In fact, if x, y ∈ Z p satisfy |x -y| p ≤ p -1-Φ(n-1) = p -2n for some positive integer n, then |f (x) -f (y)| p ≤ p -n .
In what follows, we check that Theorem 3.2 is applicable to f . Putting h = 0, n 0 = 0, and u = -a 0 , we see

u < p 1+Φ(n0) = p 2 , f (u) ≡ 0 (mod p 1+h+n0 ).
Moreover, let m, n, i be nonnegative integers with 0 ≤ m < p 1+Φ(n) = p 2n+2 and 1 ≤ i ≤ p -1. Then we have

f m + i • p 1+Φ(n) -f (m) = i • p n+1 . Observe that τ (m + i • p 1+Φ(n) ) = n + 1 by p 1+Φ(n) ≤ m + i • p 1+Φ(n) < p 1+Φ(n+1) . Thus the number b m + i • p 1+Φ(n) (≡ i (mod p))
satisfies (3.5) with S(n) = {1, 2, . . . , p -1} for any n ≥ n 0 = 0. Similarly, (3.5) with S(n) = {p + 1, p + 2, . . . , 2p -1} holds for any n ≥ n 0 = 0. In fact, we get for any 1 ≤ i ≤ p -1 that

f m + (i + p) • p 1+Φ(n) -f (m) = i • p n+1 and that τ (m + (i + p) • p 1+Φ(n) ) = n + 1.
Example 3.2. Let p = 5 and a ∈ Z 5 be fixed, and let f : Z 5 → Z 5 be defined by

f (x) = a + ∞ j=0 x 3 2j 5 j .
In the same way as in Example 3.1, we have f ∈ F(Φ), where Φ(n) := 2n + 1 for any nonnegative integer n.

Observe that if m, n, i are nonnegative integers with 0 ≤ m < 5 2n+2 and 1 ≤ i ≤ 4, then we have

f m + i • 5 1+Φ(n) -f (m) = i 3 • 5 n+1 .
Moreover, the map φ : Z/5Z → Z/5Z with φ(x mod 5Z) = x 3 mod 5Z is bijective. Thus, in the same way as in Example 3.1, we can verify that Theorem 3.2 is applicable to f , where h = 0, n 0 = 0, u is a unique integer with 0 ≤ u ≤ 4 and a + u 3 ≡ 0 (mod 5), and S(n) = {1, 2, 3, 4} for any n ≥ n 0 = 0.

We give an example of Theorem 3.2 satisfying h = 0 in Section 4.

Approximability of continuous functions

In this section we use notation defined in Sections 2 and 3. Let f : Z p → Z p be a function and u ∈ Z p . Recall for a positive integer s that f is differentiable modulo p s at u if there exists a p-adic number ∂ s f (u) satisfying the following: If n is a sufficiently large integer, then for any u ∈ Z p , we have

f (u + p n u ) ≡ f (u) + p n u ∂ s f (u) (mod p n+s ). (4.1)
Axelsson and Khrennikov showed for 1-Lipschitz functions f that if |∂ s f (u)| p = 1, then the Hensel's lifting process can be used (Theorem 2.4 and Corollary 2.6 in [START_REF] Axelsson | Generalization of Hensel's lemma: Finding the roots of p-adic Lipschitz functions[END_REF]).

For the application of Theorem 3.2, we now modify the notion of differentiability modulo p s to consider the case where f is a general continuous function, using a strictly increasing function Φ : N → N. Let u ∈ Z p . We call f approximable at u with respect to Φ if there exist nonnegative integers h = h(u), l = l(u), and a sequence (δ n f )(u) (n ≥ l) of p-adic numbers satisfying the following: For any integer n ≥ l and u ∈ Z p , we have

f u + p 1+Φ(n-1) u ≡ f (u) + p h+n u • (δ n f )(u) (mod p h+n+1 ). (4.2)
The approximability of continuous functions generalizes the differentiability modulo p s . Thus, Corollary 1 is also applicable to differentiable function modulo p s . In fact, let Φ = Id and let f be a continuous function which is differentiable modulo p s at u. Let h = s -1. Then (4.1) implies that

f (u + p n u ) = f u + p 1+Φ(n-1) u ≡ f (u) + p h+n u • (δ n f )(u) (mod p h+n+1 ), where (δ n f )(u) = ∂ h+1 f (u)/p h .
In order to apply Theorem 3.2 we will make use of the fact that (δ n f )(u) is a unit in Z p . Let Λ be a subset of Z p . We call f uniformly approximable on Λ with respect to Φ if f is approximable at any u ∈ Λ with respect to Φ and if h(u), l(u) are constants on Λ which we call h(Λ) and l(Λ) in that case. COROLLARY 1. Let Φ : N → N be a strictly increasing function and f ∈ F(Φ). Let n 0 , u ∈ N with u < p 1+Φ(n0) . Assume that f is uniformly approximable on the set

Λ := u ∈ Z p u ≡ u (mod p 1+Φ(n0) )
with respect to Φ. Moreover, assume that

n 0 + 1 ≥ l(Λ), f (u ) ≡ 0 (mod p h(Λ)+n0+1 ) and that |(δ n f )(u )| p = 1
for any n ≥ n 0 and u ∈ Λ. Then there exists a unique ξ ∈ Z p such that

f (ξ) = 0, ξ ≡ u (mod p 1+Φ(n0) ),
and such that, for any n ≥ n 0 , ρ(ξ; n + 1) ∈ {0, 1, . . . , p -1}.

Proof. We apply Theorem 3.2 with h = h(Λ) and S(n) := {1, . . . , p -1} for all n ≥ n 0 . Since f (u) ≡ 0 (mod p h(Λ)+n0+1 ) by the assumption of Corollary 1, it suffices to check (3.5) and (3.9). Assume that n, m, i ∈ N satisfy n ≥ n 0 , m < p 1+Φ(n) , m ≡ u (mod p 1+Φ(n0) ), and 1

≤ i ≤ p -1. Since τ (m + ip 1+Φ(n) ) = n + 1, we see by (4.2) and by n + 1 ≥ n 0 + 1 ≥ l(Λ) that b(m + ip 1+Φ(n) ) = p -n-1 (f (m + ip 1+Φ(n) ) -f (m)) ≡ p h(Λ) i • (δ n+1 f )(m) (mod p h(Λ)+1 ), which implies (3.5) by |(δ n f )(m)| p = 1. Now, let m be an integer with m ≥ p 1+Φ(n0) , m ≡ u (mod p 1+Φ(n0) ). Put u := m -M (m) and n := τ (m) -1 ≥ n 0 . Recall that M (m) = Φ(n+1)
i=Φ(n)+1 m i p i and therefore u := p -1-Φ(n) M (m) is an integer. Thus, we see by u ∈ Λ, (4.2) and n + 1 ≥ n 0 + 1 ≥ l(Λ) that f (u + p 1+Φ(n) u ) ≡ f (u ) + p h(Λ)+n+1 u • (δ n+1 f )(u ) (mod p h(Λ)+n+2 ).

Finally, since m = u + p 1+Φ(n) u we obtain b(m) = p -n-1 (f (u + p 1+Φ(n) u ) -f (u )) ≡ p h(Λ) u • (δ n+1 f )(u ) ≡ 0 (mod p h(Λ) ), which implies (3.9). Note that in the case of p = 2 the value of h is different from 0. First, there exists u ∈ Z p with f (u) ≡ 0 (mod p h+n0+1 ).

Let Λ := {u ∈ Z p | u ≡ u (mod p 1+Φ(n0) )}. We show that f is uniformly approximable on Λ with respect to Φ with h(Λ) = h, l(Λ) = l and (δ n f )(x) = 2 if p = 2, 1 if p = 2 (4.3) for any x ∈ Λ. Thus, Corollary 1 is applicable to f . Let x ∈ Λ. Let n be an integer with n ≥ l and y ∈ Z p . Since Note that x 0 ≡ 1 (mod p) by x ∈ Λ. If p is odd, then (4.4) implies that f x + p 1+Φ(n) y -f (x) ≡ 2x 0 y 0 p n+1 ≡ 2yp n+1 (mod p n+2 ). (4.5)

In the case of p = 2, we get by n ≥ 1 that f x + 2 1+Φ(n) y -f (x) ≡ 2x 0 y 0 • 2 n+1 ≡ y2 n+2 (mod 2 n+3 ). (4.6) Thus, (4.5) and (4.6) imply the approximability and (4.3).

PROPOSITION 3 . 1 .

 31 Let Φ : N → N be a strictly increasing function and f : Z p → Z p a continuous function. Then f ∈ F(Φ) if and only if, for any nonnegative integer m, v p (B(Φ, f ; m)) ≥ τ (Φ; m). (3.2) REMARK 1. In what follows, we consider the case where Φ and f are fixed. For simplification, we also use the notation B(m), τ (m), χ(m; x), M (m) instead of B(Φ, f ; m), τ (Φ; m), χ(Φ, m; x), M (Φ; m). Proof of Proposition 3.1. First, assume that f ∈ F(Φ). Let m be a nonnegative integer. For the proof of (3.2), we may assume that τ (m) ≥ 1. Observe by the definition of M (m) that v p m -(m -M (m)) = v p (M (m)) ≥ 1 + Φ(-1 + τ (m)). Applying (3.1) with x = m, y = m -M (m) and n = τ (m), we see v p (B(m)) ≥ τ (m) by (2.4), which implies (3.2).

  and that v p (f (x) -f (y)) ≥ n, which implies that f ∈ F(Φ) because n is an arbitrary positive integer. In what follows, for any f ∈ F(Φ) and m ∈ N, put b(m) = b(Φ, f ; m) := p -τ (Φ;m) B(Φ, f ; m) ∈ Z p (3.3) by Proposition 3.1. Moreover, for any p-adic integer x and nonnegative integer j, put ρ(x; j) := p -1-Φ(j-1)

(3. 5 )

 5 Then there exists ξ ∈ Z p such that f (ξ) = 0,(3.6) ξ ≡ u (mod p 1+Φ(n0) ),(3.7) and such that, for any n ≥ n 0 , ρ(ξ; n + 1) ∈ {0} ∪ S(n). (3.8) Assume further that, for any integer m with m ≥ p 1+Φ(n0) and m ≡ u (mod p 1+Φ(n0) ), we have b(Φ, f ; m) ≡ 0 (mod p h ). (3.9) Then ξ ∈ Z p satisfying (3.6), (3.7) and (3.8) is unique.

Example 4 . 1 . 2 .

 412 Let a ∈ Z p be fixed. If p = 2, then assume that a ≡ 1 (mod p). If p = 2, then suppose that a ≡ 1 (mod 8). For any x ∈ Z p , put f (x) := -a + Then we have f ∈ F(Φ), where Φ(n) = 2n + 1 for any nonnegative integer n. Putn 0 = h = 0 if p = 2

xxx

  + p 1+Φ(n) y = 2n+1 j=0 x j p j + ∞ j=2n+2 (x j + y j-2n-2 )p j ,we get after a direct calculationf x + p 1+Φ(n) y -f (x) 2j p j + ∞ j=n+1 (x 2j + y 2j-2n-2 )p j 2j p j • ∞ j=n+1y 2j-2n-2 p j (mod p 2n+2 ).(4.4)

Acknowledgements

The first author is supported by JSPS KAKENHI Grant Number 15K17505. The second author acknowledges the support of the bilateral project ANR-FWF (France-Austria) called MUDERA (Multiplicativity, Determinism, and Randomness), ANR-14-CE34-0009.


Lukas Spiegelhofer

Thomas Stoll

THE SUM-OF-DIGITS FUNCTION ON ARITHMETIC PROGRESSIONS

Keywords:

Let s2 be the sum-of-digits function in base 2, which returns the number of non-zero binary digits of a nonnegative integer n. We study s2 along arithmetic subsequences and show that -up to a shift -the set of m-tuples of integers that appear as an arithmetic subsequence of s2 has full complexity.

Results

The binary sum-of-digits function s 2 is an elementary object studied in number theory. It is defined by the equation

s 2 (ε ν 2 ν + • • • + ε 0 2 0 ) = ε ν + • • • + ε 0 ,
where ε i ∈ {0, 1} for 0 ≤ i ≤ ν. Despite the simplicity of definition, the behaviour of s 2 on arithmetic progressions is not fully understood. Cusick's conjecture on the sum-ofdigits function [START_REF] Drmota | On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t[END_REF][START_REF] Spiegelhofer | Approaching Cusick's conjecture on the sum-of-digits function[END_REF] concerns this area of research: for an integer t ≥ 0, we define the limit c t = lim N →∞ 1 N |{n : 0 ≤ n < N, s 2 (n + t) ≥ s 2 (n)}| .

(The limit exists, see for example Bésineau [START_REF] Bésineau | Indépendance statistique d'ensembles liés à la fonction "somme des chiffres[END_REF]. In fact, the set in this definition is periodic with period 2 k for some k.) Cusick's conjecture states that (1.1) c t > 1/2 for all t ≥ 0. Drmota, Kauers, and the first author [START_REF] Drmota | On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t[END_REF] proved that c t > 1/2 for almost all t in the sense of asymptotic density; we also wish to note the works by Emme and Prikhod'ko [START_REF] Emme | On the Asymptotic Behavior of Density of Sets Defined by Sumof-digits Function in Base 2[END_REF] and Emme and Hubert [START_REF] Emme | Central Limit Theorem for Probability Measures Defined by Sum-ofdigits Function in Base 2[END_REF][START_REF]Normal distribution of correlation measures of binary sum-of-digits functions[END_REF], and the recent partial result by the first author [START_REF] Spiegelhofer | Approaching Cusick's conjecture on the sum-of-digits function[END_REF]. In the current note, motivated by Cusick's conjecture, we are concerned with the (m + 1)-tuple s 2 (n), s 2 (n + t), . . . , s 2 (n + mt) , where t ≥ 0 and m ≥ 1 are integers. We aim to understand the set of tuples that can occur, as n and t run. In fact, our theorem states that, up to a shift, all tuples occur. Theorem 1.1. Assume that k 1 , . . . , k m ∈ Z. There exist n and t such that for

1 ≤ ≤ m, k = s 2 (n + t) -s 2 (n).
This is a generalization of the statement that the Thue-Morse sequence t has full arithmetic complexity, meaning that every finite word ω ∈ {0, 1} L occurs as an arithmetic subsequence of t. This was first proved in [START_REF] Avgustinovich | Arithmetical complexity of infinite words[END_REF] and also follows from Müllner and the first named author [START_REF] Müllner | Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences, II[END_REF], and Konieczny [START_REF] Konieczny | Gowers norms for the Thue-Morse and Rudin-Shapiro sequences[END_REF].

Theorem 1.1 is not hard to prove for m = 1. We present three arguments leading to this fact.

(1) Assume first that k ≥ 0. Set n = 2 k+1 and t = 2 k -1. Then

s 2 (n + t) = k + 1 and s 2 (n) = 1, yielding k = s 2 (n + t) -s 2 (n). If k < 0, we set n = 2 -k+1 -1 and t = 1. Then s 2 (n) = -k +1 and s 2 (n+t) = 1, which yields s 2 (n+t)-s 2 (n) = k.
Alternatively, we may also write, as in the case m = 2 presented below, t = 2 c -1 and n = 2 c-1 (2 a -1), for positive integers a and c. We obtain s 2 (n + t) = c and s 2 (n) = a, and clearly the difference c -a runs through all integers.

(2) We have

s 2 (n + 1) -s 2 (n) = 1 -ν 2 (n + 1) ≤ 1, where ν 2 (m) = max{k ≥ 0 : 2 k | m} for m ≥ 1
(n) = |k| + 1 and n ∈ {2 +1 , . . . , 2 +2 -1} such that s 2 (n ) = |k| + 1 + k. Then s 2 (n ) -s 2 (n) = k, which implies the statement. (3) Consider the densities δ(k, t) = lim N →∞ 1 N |{n : 0 ≤ n < N, s 2 (n + t) -s 2 (n) = k}|
(as it was the case for c t , this asymptotic density exists [START_REF] Bésineau | Indépendance statistique d'ensembles liés à la fonction "somme des chiffres[END_REF]). These quantities satisfy the following recurrence [START_REF] Drmota | On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t[END_REF]:

δ(k, 1) = 2 k-2 , k ≤ 1; 0 otherwise; δ(k, 2t) = δ(k, t); δ(k, 2t + 1) = 1 2 δ(k -1, t) + 1 2 δ(k + 1, t + 1).
From this, it is very easy to show that δ(k, t) > 0 for all k ≤ s 2 (t). For k given, choose t in such a way that s 2 (t) ≥ k; the positivity of the density δ(k, t) implies that there exists an n such that

s 2 (n + t) -s 2 (n) = k. For m = 2,
it is also possible to obtain the statement by elementary considerations: consider integers a, c ≥ 1, b, d ≥ 0 and choose the integers n and t in such a way that the binary expansions look as follows:

a b n : 1 • • • 11 0 • • • 0 1 • • • 10 • • • 0 t : 1 1 • • • 1 0 • • • 01 • • • 1. c d
The sums of digits of n, n + t and n + 2t respectively are a + b, b + c + d and c + d respectively. By varying the variables, we can obtain the statement for all integers k 1 and k 2 such that k 2 ≤ k 1 . For the case k 1 < k 2 , we use the following configuration of the integers n and t, where a, d ≥ 1 and c ≥ 0:

a n : 1 • • • 11 0 • • • 0 t : 1 • • • 10 • • • 01 1 • • • 1. c d
The sums of digits of n, n + t and n + 2t are a, d and c + d respectively, and we see that we obtain all pairs (k

1 , k 2 ) ∈ Z 2 such that k 1 ≤ k 2 .
However, the method quickly experiences difficulties, as multiplication by 3 is not a shift of the binary digits anymore. While we believe that the case m = 3 can be made work by some effort, a general principle is not apparent. Therefore we choose a different approach.

We prove Theorem 1.1 by induction on m, the cases m = 1, 2 having been discussed above. Assume that m ≥ 3 and let k 1 , . . . , k m ∈ Z be given. By induction hypothesis, there exist t 0 and n 0 such that k = s 2 (n 0 + t 0 ) -s 2 (n 0 + ( -1)t 0 ) for 1 ≤ < m. Set k m = s 2 (n 0 + mt 0 ) -s 2 (n 0 + (m -1)t 0 ). We are going to show that we may vary k m by steps of ±1, thus yielding the full statement.

By concatenation of binary expansions, it is sufficient to show the following statement.

(1.2)

There exist t 1 , n 1 such that s 2 (n 1 + t 1 ) -s 2 (n 1 + ( -1)t 1 ) = 0 for 1 ≤ < m and s 2 (n 1 + mt 1 ) -s 2 (n 1 + (m -1)t 1 ) = ±1.
This concatenation is straightforward and summarized in the following lemma, which we will also use again in a moment.

Lemma 1.2. Let ≥ 1, m ≥ 1, n 0 , . . . , n k-1 and t 0 , . . . , t k-1 be nonnegative integers.

There exist nonnegative integers n and t such that

s 2 (n + t) -s 2 (n + ( -1)t) = 0≤j<k s 2 (n j + t j ) -s 2 (n j + ( -1)t j ) for 1 ≤ ≤ m.
Proof. The base case k = 1 is trivial; it is sufficient to prove the statement for k = 2, the general case following easily from repeated application of this case.

Let N be so large that n 0 + mt 0 < 2 N , and set n = 2 N n 1 + n 0 and t = 2 N t 1 + t 0 . Since no carry propagation between the digits below and above N occurs, we can add up the contribution of the two blocks in order to yield the statement.

We reduce the problem further, using this block representation again: choose t j = 1 for all 0 ≤ j < k; it is sufficient to find a k ≥ 1 and nonnegative integers n j for 0

≤ j < k such that 0≤j<k (s 2 (n j + ) -s 2 (n j + -1)) = 0, if 1 ≤ < m; ±1, if = m. (1.3)
In order to show (1.3), we use the telescoping sum

a≤j<a+2 L g(j) = s 2 (a + 2 L ) -s 2 (a) = g a/2 L ,
where g(j) = s 2 (j + 1) -s 2 (j). This representation yields for 1 ≤ ≤ m, where L is chosen such that 2

L ≤ m < 2 L+1 , 2•2 L -m+ ≤j<3•2 L -m+ g(j) = g 2 + (-m + )/2 L = g(1) = 0, if 1 ≤ < m; g(2) = 1, if = m; 2 L -m+ ≤j<2•2 L -m+ g(j) = g 1 + (-m + )/2 L = g(0) = 1, if 1 ≤ < m; g(1) = 0, if = m; 3•2 L+1 + ≤j<4•2 L+1 + g(j) = g(3) = -1 for 1 ≤ ≤ m.
The first of these three identities yields the "+"-part of (1.3) by choosing k = 2 L and n j = 2 • 2 L -m + j for 0 ≤ j < k.

The "-"-part is obtained from the second and third identities: by considering the disjoint union

J = [2 L -m, 2 • 2 L -m) ∪ [3 • 2 L+1 , 4 • 2 L+1 ), we have j∈J (s 2 (j + ) -s 2 (j + -1)) = 0, if 1 ≤ < m; -1, if = m.
The statement follows by merging the two intervals and choosing n j accordingly. This finishes the proof of our theorem.

Possible extensions

From our proof, it is possible to effectively construct integers n and t such that s 2 (n + t) -s 2 (n) = k for 1 ≤ ≤ m. In particular, this yields integers n and t such that t n+ t = ω for 1 ≤ ≤ m, where (ω 1 , . . . , ω m ) ∈ {0, 1} m and t is the Thue-Morse sequence on {0, 1}. (Note that we also used t(2 λ + n) = 1 -t(n) for n < 2 λ .) This gives a constructive result concerning the problem of full arithmetic complexity of the Thue-Morse sequence considered in [START_REF] Avgustinovich | Arithmetical complexity of infinite words[END_REF][START_REF] Konieczny | Gowers norms for the Thue-Morse and Rudin-Shapiro sequences[END_REF][START_REF] Müllner | Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences, II[END_REF].

As an extension of the presented line of research, we are interested in the proportion of cases in which s 2 (n + t) -s 2 (n) = k occurs (for 1 ≤ ≤ m). For this, we define more generally

δ(k, ε, t) = dens {n ∈ N : s 2 (n + t + ε ) -s 2 (n) = k for 1 ≤ ≤ m} ,
where k = (k 1 , . . . , k m ) ∈ Z m and ε = (ε 1 , . . . , ε m ) ∈ N m . This generalizes the array δ defined before. As in the one-dimensional case, the densities in this definition actually exist, and they satisfy the following recurrence relation:

δ(k, ε, 2t) = 1 2 δ(k , ε , t) + 1 2 δ(k , ε , t),
where

k = k -(ε mod 2), k = k + 1 -((ε + 1) mod 2), ε = ε /2 and ε = (ε + 1)/2 ; moreover, δ(k, ε, 2t + 1) = 1 2 δ(k , ε , t) + 1 2 δ(k , ε , t),
where k = k -((ε + ) mod 2), k = k + 1 -((ε + + 1) mod 2), ε = (ε + )/2 and ε = (ε + + 1)/2 . This recurrence is the reason for the introduction of ε in the definition of δ(k, ε, t). To our knowledge, these identities are new; we give the idea of proof. We have

δ(k, ε, 2t) = 1 2 dens{n ∈ N : s(2n + 2 t + ε ) -s(2n) = k for 1 ≤ ≤ m} + 1 2 dens{n ∈ N : s(2n + 2 t + ε + 1) -s(2n + 1) = k for 1 ≤ ≤ m},
and using the identities s(2n) = s(n) and s(2n + 1) = s(n) + 1, we obtain

s(2n + 2 t + ε ) = s (2(n + t + ε /2 ) + (ε mod 2)) = s n + t + ε + (ε mod 2), therefore s(2n + 2 t + ε ) -s(2n) = k is equivalent to s (n + t + ε ) -s(n) = k .
Analogous computations are valid for ε replaced by ε + 1, ε + and ε + + 1 respectively, which yields the claim. This recurrence can be used to prove statements on the densities δ(k, ε, t). The general intuitive idea is that the differences s(n+jt)-s(n), for 1 ≤ j ≤ m, should be almost independent for most t; in the light of this consideration, we consider generalizations of Cusick's conjecture and of Emme and Hubert's result [START_REF] Emme | Central Limit Theorem for Probability Measures Defined by Sum-ofdigits Function in Base 2[END_REF]. On the one hand, we may ask for multidimensional generalizations of (1.1), relating the relative sizes of the values s 2 (n), s 2 (n + t), . . . , s 2 (n + mt) to one another. We propose the following conjecture, extending (1.1).

Conjecture 1. Assume that m ≥ 1 is an integer. For an integer t ≥ 0, define

c (m) t = dens{n ∈ N : s(n) ≤ s(n + jt) for 1 ≤ j ≤ m}.
Then for all t ≥ 0, c (m) t > 1 2 m . The statement is wrong for any larger constant in place of 1/2 m . Also, define

C (m) t = dens{n ∈ N : s(n) ≤ s(n + t) ≤ s(n + 2t) ≤ • • • ≤ s(n + mt)}.
Then for all t ≥ 0,

C (m) t > 1 2 m m! .
The constant 1/(2 m m!) is maximal.

On the other hand, we could ask for the overall shape of the m-dimensional probability distribution defined by δ(•, ε, t).

Problem 1. Prove a multidimensional generalization of the theorem by Emme and Hubert [START_REF] Emme | Central Limit Theorem for Probability Measures Defined by Sum-ofdigits Function in Base 2[END_REF]: for most t, the densities dens{n ∈ N : s 2 (n+ t)-s 2 (n) = k for 1 ≤ ≤ m} should define a probability distribution that is close to a multivariate Gaussian law.

We can now understand the intuition behind the constants in Conjecture 1: a bivariate normal distribution with mean (0, 0) has one quarter of its total weight in the quadrant {(x, y) ∈ R 2 : 0 ≤ x, 0 ≤ y}, and analogous considerations hold for higher dimensions. Concerning the values C

(2) t , a bivariate normal distribution with mean (0, 0) has one eighth of its total weight in the octant {(x, y) ∈ R 2 : 0 ≤ x ≤ y}, which corresponds to the complex closed region {re 2πix : r ≥ 0, 1/8 ≤ x ≤ 1/4}. Noting the fact that s(n + 2t) ≥ s(n + t) if and only if s(n + 2t) -s(n) ≥ s(n + t) -s(n), we see

  is the 2-adic valuation of m. This formula follows by considering the number of 1s with which the binary expansion of n ends. Since s 2 (2 ) = 1 and s 2 (2 +1 -1) = + 1, we obtain the fact that s 2 (n) attains all values in {1, . . . , + 1} as n varies in {2 , . . . , 2 +1 -1}. Let k ∈ Z be given and set = 2|k|. Choose n ∈ {2 , . . . , 2 +1 -1} such that s 2

The authors acknowledge support by the project MuDeRa, which is a joint project between the FWF (Austrian Science Fund) and the ANR (Agence Nationale de la Recherche). Moreover, the first author was supported by the FWF project F5502-N26, which is a part of the Special Research Program "Quasi Monte Carlo methods: Theory and Applications"; the second author was supported by the project ANR-18-CE40-0018.

the link between the densities δ(k, ε, t) with k lying in this octant and the values C

(2) t . Concerning higher dimensions, we note that the m! sets

where σ is a permutation of {1, . . . , m}, are unions of line segments [0, z], where z = 1; they are pairwisely congruent (using a linear transformation that is a permutation matrix in the canonical base); an intersection of two distinct sets of this form has measure zero, and their union comprises a fraction 1/2 m of the unit ball in m dimensions.

We implemented the computation of the densities δ(k, ε, t) for two dimensions in the Sage computer algebra system [START_REF]The Sage Developers[END_REF], and the resulting Sage worksheet is available from the website of the first named author [10]. We obtain c

. The implementation involves nine two-dimensional arrays of rational numbers (corresponding to the nine possibilities (ε 1 , ε 2 ) ∈ {0, 1, 2} 2 ) and each of these calculations took about 5 minutes on a standard machine. We note that we did not optimize the Sage code, and certainly this computation can be sped up significantly.

Other conjectures similar to Conjecture 1 are conceivable: what about the other octants and quadrants A in the plane (including the borders)? Is it always true that 1/8 resp. 1/4 is a lower bound for the density dens{n ∈ N : s(n+t)-s(n), s(n+2t)-s(n) ∈ A}? We leave this question open for future discussion, but we note that the analogous problem in one dimension is true for almost all t: we also have

for t in a set having asymptotic density 1 [START_REF] Drmota | On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t[END_REF]. In other words, usually the median of the probability distribution defined by δ(•, t) is very close to the mean value (which is 0). We believe that ct ≥ 1/2 is true for all t, which complements Cusick's conjecture (1.1) (note that c1 = 1/2, thus there is no strict inequality).

We expect that nontrivial statements on both Conjecture 1 and Problem 1, at least for small m, can be obtained by extending the study of moments set forward by Emme and Hubert [START_REF] Emme | Central Limit Theorem for Probability Measures Defined by Sum-ofdigits Function in Base 2[END_REF]. This is certainly not easy and will introduce technical difficulties that have to be surmounted.