Irène Marcovici
email: irene.marcovici@univ-lorraine.fr

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

Pierre-Adrien Tahay
email: pierre-adrien.tahay@univ-lorraine.fr

DISCRETE CORRELATIONS OF ORDER 2 OF GENERALIZED GOLAY-SHAPIRO SEQUENCES: A COMBINATORIAL APPROACH

We introduce a family of block-additive automatic sequences, that are obtained by allocating a weight to each couple of digits, and defining the nth term of the sequence as being the total weight of the integer n written in base k. Under an additional difference condition on the weight function, these sequences can be interpreted as generalized Golay-Shapiro sequences, and we prove that they have the same correlations of order 2 as sequences of symbols chosen uniformly and independently at random. The speed of convergence is very fast and is independent of the prime factor decomposition of k. This extends recent work of Tahay. The proof relies on direct observations about base-k representations of integers and combinatorial considerations. We also provide extensions of our results to higher-dimensional block-additive sequences.

Introduction

A k-automatic sequence on a finite set G is a sequence u ∈ G N that can be computed by a deterministic finite automaton with output (DFAO) in the following way: the n-th term of the sequence is a function of the state reached by the automaton after reading the representation of the integer n in base k. Alternatively, a k-automatic sequence can also be defined as a sequence generated by a k-uniform morphism. We refer to the book of Allouche and Shallit [START_REF] Allouche | Automatic Sequences, Theory, Applications[END_REF] for a complete survey on automatic sequences.

Although automatic sequences are deterministic sequences having a very simple algorithmic description, some of them exhibit a complex behaviour. In this work, we are interested in exploring "how random" an automatic sequence can look like. There are many different ways to measure the "random aspect" of a deterministic sequence. Here, we will study families of automatic sequences having the same discrete correlations of order 2 as sequences of symbols chosen uniformly and independently at random. We also provide explicit estimates for the speed of convergence.

The sequences we will consider are block-additive sequences. They are obtained by allocating a weight to each couple of digits, and defining the nth term of the sequence as being the total weight of the integer n written in base k. This weight is obtained by sliding the representation of the integer n in base k with a window of length 2 (or more generally, of length L ≥ 1), and summing all the weights read. The name block-additive was already used in previous articles [START_REF] Drmota | Block additive functions on the Gaussian integers[END_REF][START_REF] Müllner | The Rudin-Shapiro sequence and similar sequences are normal along squares[END_REF]. With the terminology of Cateland [START_REF] Cateland | Digital sequences and k-regular sequences[END_REF], these sequences are digital sequences. In the special case where the weight matrix is a difference matrix, we will say that the automatic sequence obtained is a generalized Golay-Shapiro sequence, and prove that it has the same correlations of order 2 as a sequence of symbols chosen uniformly and independently at random. 1As we will comment on further in the article, our terminology of generalized Golay-Shapiro sequences is consistent with the definitions of [START_REF] Grant | Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences[END_REF][START_REF] Tahay | Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size[END_REF], and also intersects previous notions of generalized Golay-Shapiro sequences, such as the one of Queffélec [START_REF] Queffélec | Une nouvelle propriété des suites de Rudin-Shapiro[END_REF] (see [START_REF] Grant | Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences[END_REF] for further references). For other generalizations of the Golay-Shapiro sequence that we will not investigate here, see Allouche and Liardet [START_REF] Allouche | Generalized Rudin-Shapiro sequences[END_REF], Allouche and Shallit [START_REF] Allouche | Complexité des suites de Rudin-Shapiro généralisées[END_REF], and Mauduit and Rivat [START_REF] Mauduit | Prime numbers along Rudin-Shapiro sequences[END_REF]. More specifically, we will not treat sequences such as those proposed by Mendès France that count 1w1 in base 2 where w is an arbitrary finite non-empty binary string (these sequences are investigated in [2, Section 3]). Some alternative ddimensional extensions of the Golay-Shapiro sequence are also proposed in [START_REF] Frank | Substitution sequences in Z d with a non-simple Lebesgue component in the spectrum[END_REF] and [START_REF] Barbé | Correlation and spectral properties of higher-dimensional paperfolding and Rudin-Shapiro sequences[END_REF].

As in the articles of Grant et al. [START_REF] Grant | Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences[END_REF] and Tahay [START_REF] Tahay | Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size[END_REF], we study the correlations of order 2 of generalized Golay-Shapiro sequences, but rather than making use of exponential sums, we here only employ direct arguments relying on the basek decomposition of the integers n and n + r, for a fixed r. This approach highlights the combinatorial role played by the difference condition defining a difference matrix, and allows to obtain more precise estimates on the correlations of order 2. Furthermore, in addition to studying the asymptotic proportion of integers n satisfying u n = u n+r , we provide results on the proportion of integers for which (u n , u n+r ) = (i, j), for any possible value of the couple (i, j) ∈ G 2 . Precisely, we prove that the limit is equal to 1/|G| 2 for all (i, j) ∈ G 2 and for any r ∈ N \ {0}, as for an i.i.d. sequence of symbols uniformly drawn in G. After considering the one-dimensional case, we also mention extensions of our results to higher-dimensional block-additive sequences.

Definitions and presentation of the results

In all the article, we denote by N the set of non-negative integers, and for an integer n ≥ 2, we use the notation Z n = Z/nZ.

Block-additive sequences of rank 2

For k ∈ N \ {0}, we define Σ k = {0, . . . , k -1}, and we denote by [n] k the representation of the integer n ∈ N in base k. By definition, it is the unique sequence x = (x i ) i∈N ∈ Σ N k containing finitely many non-zero values, such that

n = i∈N x i k i .
We will write

[n] k = x 0 x 1 x 2 x 3 • • • .
We also introduce the notation n = min{i ∈ N : x j = 0 for all j > i}, and we define

σ k (n) = i∈N x i = n i=0
x i , the k-ary sum-of-digits function.

Definition 1. Let (G, +) be a finite abelian group, let k ∈ N \ {0}, and let f : Σ k × Σ k → G be a function satisfying f (0, 0) = 0. We say that the sequence u = (u n ) n∈N ∈ G N is a block-additive sequence (of rank 2) in base k of weight function (or matrix) f if for any integer n ∈ N, we have

u n = i∈N f (x i , x i+1 ), where [n] k = x.
Example 1 (Prouhet-Thue-Morse sequence). The Prouhet-Thue-Morse sequence (or Thue-Morse sequence) is given by

u n ≡ σ 2 (n) (mod 2), n ∈ N.
It is a block-additive sequence in base k = 2, with G = Z 2 , and weight function

f : Σ 2 × Σ 2 → G defined by f (i, j) = i, for any (i, j) ∈ G 2 .
The first terms are given by u = (0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, . . .). We represent below a DFAO computing this sequence.

q 0 |0 start q 1 |1 0 1 1 0
Example 2 (Classical Golay-Shapiro sequence). The (classical) Golay-Shapiro sequence (or Rudin-Shapiro sequence) on G = Z 2 can be defined as the blockadditive sequence in base k = 2 of weight function f : Σ 2 × Σ 2 → G given by f (i, j) = ij, for any (i, j) ∈ G 2 . In other words, u n gives the parity count of the number of (possibly overlapping) occurrences of the block 11 in the binary expansion of n. The first terms are given by u = (0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, . . .).

The following proposition is straightforward. For the sake of completeness, we include the proof.

Proposition 1. If a sequence is block-additive in base k, then it is a k-automatic sequence. Proof. Let Q = G × Σ k , q 0 = (0, 0), let δ : Q × Σ k → Q be defined by δ((g, i), j) = (g + f (j, i), j),
and let τ : Q → G be defined by τ (g, i) = g. The DFAO (Q, Σ k , δ, q 0 , τ ) computes the block-additive sequence u = (u n ) n∈N of weight function f , by reading the representation of the integer n in base k starting with the most significant digit, and using the output map τ . Remark 1. Alternatively, a block-additive sequence has the following morphic description. Again, let Q = G × Σ k and q 0 = (0, 0), and let φ :

Q * → Q * be the k-uniform morphism satisfying, for a state s = (g, i) ∈ Q, φ(s) = s 0 • • • s k-1
, with s j = (g + f (j, i), j). Consider the fixed point φ ω (q 0 ) ∈ Q N . Then, the letter-to-letter projection of φ ω (q 0 ) by τ is the block-additive sequence of the function f . With the notations q 0 = (0, 0), q 1 = (0, 1), q 2 = (1, 0), q 3 = (1, 1), the 2-uniform morphism described above is here given by φ(q 0 ) = q 0 q 1 , φ(q 1 ) = q 0 q 2 , φ(q 2 ) = q 3 q 1 , φ(q 3 ) = q 3 q 2 , with τ (q 0 ) = τ (q 1 ) = 0, τ (q 2 ) = τ (q 3 ) = 1.

Difference matrices and generalized Golay-Shapiro sequences

Definition 2. Let (G, +) be a finite abelian group, and let

k ∈ N \ {0}. A difference matrix of size k is a matrix D = (d(i, j)) (i,j)∈Σ k ×Σ k ∈ G Σ k ×Σ k satis-
fying the following difference condition: for every (i, j) ∈ Σ k × Σ k with i = j, and every g ∈ G,

card h ∈ Σ k : d(i, h) -d(j, h) = g = k |G| .
In other words, D is a difference matrix if for any (i, j) ∈ Σ k ×Σ k with i = j, the set {d(i, h) -d(j, h) : h ∈ Σ k } contains every element of G equally often. Note that the difference condition requires the integer k to be a multiple of |G|. We introduce the notation π = k/|G|, and thus we have π ∈ N \ {0}. We denote by D(G, k) the set of difference matrices of size k over the group G. Definition 3. A block-additive sequence is a generalized Golay-Shapiro sequence if its weight function f is such that the matrix (f (i, j)

) (i,j)∈Σ k ×Σ k ∈ G Σ k ×Σ k is a difference matrix. Example 4.
1. The Thue-Morse sequence is not a generalized Golay-Shapiro sequence, since its weight function is given by the matrix 0 0 1 1 , which

does not belong to D(Z 2 , 2).

2. The classical Golay-Shapiro sequence is a generalized Golay-Shapiro sequence, since its weight function is given by the matrix 0 0 0 1 , which belongs to D(Z 2 , 2).

Let us present different ways to construct difference matrices, and thus to define generalized Golay-Shapiro sequences.

Example 5. Let p be a prime number, and let G = Z p . Then, the matrix D = (d(i, j)) (i,j)∈Σp×Σp defined by d(i, j) ≡ ij (mod p) is a difference matrix. The block-additive sequences thus obtained correspond to Queffélec's generalization of the Golay-Shapiro sequence [START_REF] Queffélec | Une nouvelle propriété des suites de Rudin-Shapiro[END_REF]Section 4]. By definition, if [n] p = x, we have u n ≡ i∈N x i x i+1 (mod p).

• As a particular case, for p = 2, the difference matrix is given by 0 0 0 1 , and we recover the classical Golay-Shapiro sequence.

• For p = 3, the difference matrix is given by

  0 0 0 0 1 2 0 2 1   .
Example 6. For k = 3, another example of a difference matrix on G = Z 3 is given by

  0 1 1 1 0 1 1 1 0   .
In the sequence obtained, the term u n counts (modulo 3) the number of blocks of distinct digits in the base-3 decomposition of the integer n.

It can be seen that for an even integer k ≥ 4, there exists no difference matrix of size

k on G = Z k . Indeed, if k is even, we have k-1 i=0 i ≡ k/2 (mod k). But if k-1 h=0 (d(i 1 , h) -d(i 2 , h)) ≡ k/2 (mod k) and k-1 h=0 (d(i 2 , h) -d(i 3 , h)) ≡ k/2 (mod k), then k-1 h=0 (d(i 1 , h) -d(i 3 , h)) ≡ 0 (mod k)
, so that we obtain a contradiction.

However, the following theorem shows the existence of difference matrices at least for all powers of prime numbers. We include the proof for the sake of clearness.

Theorem 1. [10, Theorem 6.6] For any prime number p and any integers m, n ∈ N \ {0} such that m ≤ n, there exists a finite abelian group G of order p m such that the set D(G, p n ) is non-empty.

Proof. Let H = F p m , and G = F p n be the finite fields with respectively p m and p n elements. We can represent the elements of G by polynomials of the form

β 0 + β 1 x + • • • + β n-1 x n-1 , with β 0 , . . . , β n-1 ∈ Z p .
The group (H, +) can be seen as the subgroup of (G, +) made of the polynomials of degrees smaller or equal to m. Let ϕ : G → H be the function which maps the element

β 0 + β 1 x + • • • + β n-1 x n-1 to the element β 0 + β 1 x + • • • + β m-1 x m-1 , and for two polynomials (α(x), β(x)) ∈ G 2 , let d(α(x), β(x)) = ϕ(α(x) • β(x))
, where • denotes the multiplication in the field G. Then, one can check that the matrix D = (d(i, j)) (i,j)∈Σ p n ×Σ p n (we identify Σ p n with G, using any bijection) is a difference matrix on (G, +) ∼ = ((Z p ) n , +).

Note that there exist difference matrices which do not belong to the families described in the proof of Theorem 1 (see [11, p.127] and [10, Table 6.37]). For example, the matrix

        0 0 0 0 0 0 0 0 1 1 2 2 0 1 0 2 1 2 0 1 2 0 2 1 0 2 1 2 0 1 0 2 2 1 1 0        
is an element of D(Z 3 , 6) that is not covered by Theorem 1.

The enumeration and the classification of difference matrices is a complex task. We refer to [START_REF] Hedayat | Orthogonal Arrays[END_REF][START_REF] Lampio | Classification of difference matrices and complex Hadamard matrices[END_REF] for an indepth study of these questions and various examples of difference matrices.

Main results

We can now state our main results, in the one-dimensional case. We use the notation log k (N ) for the logarithm of N to base k. Theorem 2. If u is a generalized Golay-Shapiro sequence, then for any r ∈ N \ {0}, g ∈ G, and N ∈ N,

1 N card n ∈ 0, N -1 : u n+r -u n = g - 1 |G| ≤ r k 1 + log k (N ) N .
The limit 1/|G| is thus the same as for an i.i.d. sequence of symbols uniformly distributed in G. But the convergence is here much faster than in the random case, since the error term is of order log(N )/N , while for i.i.d. sequences, the central limit theorem tells us that it is of order 1/ √ N .

Remark 2. For k prime or a prime power, the bound in Theorem 2 is the same as the one obtained by Tahay [START_REF] Tahay | Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size[END_REF]Theorem 4]. This is natural since the underlying objects (generalizations of the Golay-Shapiro sequence) are the same. However, our generalization of the Golay-Shapiro sequence to other composed k is different from Tahay [START_REF] Tahay | Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size[END_REF]: it is directly based on one single difference matrix of size k, while Tahay's construction uses the prime factor decomposition of k and, as a side effect, the error term in his result is N -1/d where d denotes the number of different primes appearing in the prime factor decomposition of k [15, Theorem 5]. The size of our error term for our generalized objects is log(N )/N , as N → ∞, which is much smaller for fixed r and is independent of the arithmetic structure of k.

Theorem 3. If u is a generalized Golay-Shapiro sequence, then for any r ∈ N \ {0}, and any

(i, j) ∈ G 2 , lim N →∞ 1 N card n ∈ 0, N -1 : (u n , u n+r ) = (i, j) = 1 |G| 2 .
Remark 3. Tahay obtained several results on the mean value of the discrete correlation coefficients along the integers. The discrete correlation coefficient equals 0 if two symbols are identical, and 1 otherwise [15, Definition 1]. Theorem 3 gives a local result that is uniform in the values of the two symbols.

Discrete correlations of order 2 of generalized Golay-Shapiro sequences

The aim of this section is to prove Theorem 2 and Theorem 3. Namely, we prove that generalized Golay-Shapiro sequences have the same discrete correlations of order 2 as i.i.d. sequences of symbols, and give a tight estimate of the speed of convergence.

Frequencies of letters in generalized Golay-Shapiro sequences

In this section, we present some first general results on generalized Golay-Shapiro sequences, that we will need afterwards.

Lemma 1. A generalized Golay-Shapiro sequence is a primitive morphic sequence.

Proof. As in the proof of Proposition 1, let Q = G×Σ k , and let M be the matrix indexed by Q and with values in {0, 1}, defined by M ((g, i), (g , i )) = 1 if and only if there exists j ∈ Σ k such that (g , i ) = (g + f (j, i), j). Equivalently, M ((g, i), (g , i )) is given by the number of j ∈ Σ k such that (g , i ) = (g + f (j, i), j). This matrix thus describes the allowed transitions in the DFAO given in the proof of Proposition 1, or equivalently, the incidence matrix of the k-uniform morphism defined in Remark 1. We prove that all the entries of M 2|G|+3 are positive (the bound might be not optimal), where we recall that the entries of M n correspond to the number of paths (i.e. consecutive transitions in the DFAO) of length n from one state to another.

Let s 1 = (g 1 , i 1 ) and s 2 = (g 2 , i 2 ) be two elements of Q. By the difference condition, there exists at least one

h ∈ G such that f (1, h) -f (0, h) = g 2 - g 1 -f (0, 1) -f (0, i 1 ) -f (i 2 , 0)
. From the state i 1 , let us read in the DFAO the sequence (0, h, 0, h, 0, h, . . . , 0, h, 0, h, 1, 0, i 2 ), made of |G| times the pattern (0, h), followed by the pattern (1, 0, i 2 ). Then, the new state will be s 2 , since

f (0, i1) + f (h, 0) + f (0, h) + f (h, 0) + • • • + f (0, h) + f (h, 0) + f (1, h) + f (0, 1) + f (i2, 0) = |G|f (h, 0) + (|G| -1)f (0, h) + f (1, h) + f (0, 1) + f (0, i1) + f (i2, 0) = f (1, h) -f (0, h) + f (0, 1) + f (0, s1) + f (s2, 0) = g2 -g1.

The conclusion follows.

Proposition 2. If u is a generalized Golay-Shapiro sequence, then any pattern has a frequency in the sequence u. Furthermore, the frequency of each element of G (corresponding to patterns of length 1) is equal to 1/|G|.

Proof. The existence of the frequencies for all patterns follows from the fact that the sequence φ ω (q 0 ) ∈ Q N is a primitive morphic sequence, where φ is the morphism given in Remark 1. Furthermore, each element of Q has exactly k preimages, since to state s = (g, j) ∈ Q, one can arrive from the state (gf (j, i), i), for any i ∈ G (by reading j). The vector of frequencies being the unique eigenvector to the eigenvalue k, all the elements of Q have the same frequency in φ ω (q 0 ), and consequently, each element of G has the same frequency in the image of φ ω (q 0 ) by τ .

Fibre of an integer

We now introduce the notion of fibre of an integer, that will be useful in our context to study correlations of order 2 of generalized Golay-Shapiro sequences.

Let r ∈ N \ {0} be a fixed integer. For n ∈ N, let us introduce the representations of n and n + r in base k as follows

[n] k = x, [n + r] k = y.
We define the integer c n = min{i ∈ N : x j = y j for all j > i}.

Note that c n depends on r, but that for the sake of shortness, we do not mention this dependence in the notation. The integer c n measures how far the carry propagates when adding r to n. By definition, x cn = y cn and for every j > c n , we have x j = y j . We illustrate the definition of c n below:

[n] k = x 0 x 1 • • • x cn x cn+1 x cn+2 • • • [n + r] k = y 0 y 1 • • • y cn x cn+1 x cn+2 • • • (1)
We define the fibre of n as the set

F r (n) = {m ∈ N : x = [m] k satisfies x i = x i for every i ∈ N \ {c n + 1}} = {n + (α -x cn+1 ) k cn+1 : α ∈ Σ k }.
Thus, we have

F r (n) = { x 0 x 1 • • • x cn 0 x cn+2 x cn+3 • • • , x 0 x 1 • • • x cn 1 x cn+2 x cn+3 • • • , x 0 x 1 • • • x cn 2 x cn+2 x cn+3 • • • , . . . x 0 x 1 • • • x cn k -1 x cn+2 x cn+3 • • • }. Note that if m ∈ F r (n), then c m = c n , so that m ∈ F r (n) ⇐⇒ n ∈ F r (m).
Furthermore, let m ∈ F r (n), and let x = [m] k , y = [m + r] k . Then by definition, y cn+1 = x cn+1 , and for every i ∈ N \ {c n + 1}, we have y i = y i , as represented below:

[m] k = x = x 0 x 1 • • • x cn x cn+1 x cn+2 • • • [m + r] k = y = y 0 y 1 • • • y cn x cn+1 x cn+2 • • • (2)
Let u be a block-additive sequence in base k of weight f , and recall the notation π = k/|G|. For n ∈ N, we also introduce the notation ∆ r (n) = u n+r -u n . Proposition 3. If u is a generalized Golay-Shapiro sequence, then for any n ∈ N, and any g ∈ G, we have

card{m ∈ F r (n) : ∆ r (m) = g} = π.
Proof. By definition of a block-additive sequence, with the notations of Equation (1), we have

∆ r (n) = i∈N f (y i , y i+1 ) - i∈N f (x i , x i+1 ) = cn i=0 f (y i , y i+1 ) -f (x i , x i+1 ) . If m ∈ F r (n), with the notations of Equation (2), we have ∆ r (m) = cn i=0 (f (y i , y i+1 ) -f (x i , x i+1 )), so that ∆ r (m) -∆ r (n) = f (y cn , y cn+1 ) -f (x cn , x cn+1 ) -f (y cn , y cn+1 ) -f (x cn , x cn+1 ) = f (y cn , x cn+1 ) -f (x cn , x cn+1 ) -f (y cn , x cn+1 ) -f (x cn , x cn+1 ) . It follows that for all g ∈ G, card{m ∈ F r (n) : ∆ r (m)-∆ r (n) = g} = card α ∈ Σ k : f (y cn , α)-f (x cn , α)-A n = g , with A n = f (y cn , x cn+1 ) -f (x cn , x cn+1 ).
Consequently, if u is a generalized Golay-Shapiro sequence, then for any n ∈ N, and any g ∈ G, we have

card{m ∈ F r (n) : ∆ r (m) -∆ r (n) = g} = π,
and Proposition 3 follows.

Proof of Theorem 2

Using the notion of fibre developed above, we obtain the following proposition, from which Theorem 2 directly follows, since

g∈G card n ∈ 0, N -1 : ∆ r (n) = g = N . Proposition 4. If u is a generalized Golay-Shapiro sequence, then for any g ∈ G, card n ∈ 0, N -1 : ∆ r (n) = g ≥ πN k -π r k -π r σ k (N ) ≥ N |G| -π r k(1 + log k (N )).
Proof. Let N ∈ N \ {0}, and let a = [N ] k . We determine the conditions under which an integer n ∈ 0, N -1 satisfies F r (n) ⊂ 0, N -1 . Recall the notation N = min{i ∈ N : a i = 0 for all j > i}. We can thus write

[N ] k = a 0 a 1 • • • a N -1 a N 0 0 • • • • If n = a N k N + α k N -1 + γ, for some α ≤ k -1, a N < a N , and γ < k N -1 -r, then c n ≤ N -2, so that F r (n) ⊂ 0, N -1 . [n] k = x 0 x 1 • • • x N -2 γ<k N -1 -r α a N <a N 0 0 • • • [n + r] k = x 0 x 1 • • • x N -2 α a N 0 0 • • • • If n = a N k N + a N -1 k N -1 + α k N -2 + γ, for some α ≤ k -1, a N -1 < a N -1 , and γ < k N -2 -r, then c n ≤ N -3, so that F r (n) ⊂ 0, N -1 . [n] k = x 0 x 1 • • • x N -3 γ<k N -2 -r α a N -1 <a N -1 a N 0 0 • • • [n + r] k = x 0 x 1 • • • x N -3 α a N -1 a N 0 0 • • • • If n = a N k N + a N -1 k N -1 + a N -2 k N -2 + α k N -3 + γ, for some α ≤ k -1, a N -2 < a N -2 , and γ < k N -3 -r, then c n ≤ N -4, so that F r (n) ⊂ 0, N . [n] k = x 0 x 1 • • • x N -4 γ<k N -3 -r α a N -2 <a N -2 a N -1 a N 0 0 • • • [n + r] k = x 0 x 1 • • • x N -4 α a N -2 a N -1 a N 0 0 • • •
• And so on, the last condition that will be of interest for us being that if

n = a N k N + a N -1 k N -1 + . . . + a r +3 k r +3 + a r +2 k r +2 + α k r +1 + γ, for some α ≤ k -1, a r +2 < a r +2 , and γ < k r +1 -r, then c n ≤ r , so that F r (n) ⊂ 0, N -1 .
The number of different integers n ∈ 0, N -1 satisfying F r (n) ⊂ 0, N -1 that we have exhibited above is equal to

a N k(k N -1 -r) + a N -1 k(k N -2 -r) + a N -2 k(k N -3 -r) + . . . + a r +2 k(k r +1 -r) = N -(a r +1 k r +1 + a r k r + . . . + a1k + a0) -r k (a N + a N -1 + a N -2 + . . . + a r +2 ) > N -r k 2 -r k σ k (N ).
For the last inequality, observe that a r +1 k r +1 + a r k r + . . . + a 1 k + a 0 < k r +2 ≤ r k 2 . Proposition 4 then directly follows from Proposition 3.

Correlation matrix

In order to prove Theorem 3, we first introduce the notion of correlation matrix, and formulate the previous results using this terminology.

Let u ∈ G N be a fixed sequence. For r ∈ N \ {0}, (i, j) ∈ G 2 and n ∈ N, we define

δ r i,j (n) = 1 if (u n , u n+r ) = (i, j), 0 otherwise; and C r i,j (N ) = 1 N N -1 n=0 δ r i,j (n).
As a consequence of Proposition 2, if u is a generalized Golay-Shapiro sequence, then for any r ∈ N \ {0} and (i, j) ∈ G 2 , the sequence C r i,j (N ) converges when N goes to infinity, so that we can also introduce

C r i,j = lim N →∞ C r i,j (N ).
We define the correlation matrix as the matrix C r = (C r i,j ) (i,j)∈G 2 of size |G| × |G|. By Proposition 2, for any i ∈ G, the asymptotic frequency of the symbol i is equal to

j∈G C r i,j = 1 |G| .
As a consequence of Proposition 4, we obtain the following results.

Corollary 1. If u is a generalized Golay-Shapiro sequence, then for any

(i, j) ∈ G 2 , ∈G C r i-,j-(N ) ≥ 1 |G| -π r k 1 + log k (N ) N .
Corollary 2. If u is a generalized Golay-Shapiro sequence, then for any

(i, j) ∈ G 2 , ∈G C r i-,j-= 1 |G| .
Proof. It is a consequence from Corollary 1 and the observation that

(i,j)∈G 2 C r i,j = 1.
Note that this result refines the estimates of Tahay concerning the discrete correlation coefficient (cf. Remark 3) that detects whether two symbols differ or not. In our language, he proved that i∈G C r i,i = 1 |G| .

Proof of Theorem 3

With the notations above, Theorem 3 is equivalent to the next proposition, that we now prove. Note that this result is stronger than Corollary 2 as it gives the values of the individual terms in the sum.

Proposition 5. If u is a generalized Golay-Shapiro sequence, then for any

(i, j) ∈ G 2 , C r i,j = 1 |G| 2 .
Proof. Let us fix some α ∈ Σ k and consider the integers n ∈ 0, k 2N +1 -1 that are such that the base-k decomposition

x = [n] k of n satisfies x N +1 = α. In other words, n = m 1 k N +1 + α k N + m 2 , for some integers m 1 , m 2 ∈ 0, k N -1 .
Assuming furthermore that m 2 < k N -r, we will have c n < N , so that

(u n , u n+r ) = (u km1+α , u km1+α ) + (u αk N +m2 , u αk N +m2+r ),
by definition of a block-additive sequence.

The proof will be based on the following idea: when taking independently at random some integers m 1 , m 2 uniformly distributed in 0, k N -1 , the distribution of u km1+α converges to the uniform distribution on G when N goes to infinity, while for the second term (u αk N +m2 , u αk N +m2+r ), the distribution is asymptotically given by the values C i,j of the correlation matrix. Now, we have (u n , u n+r ) = (i, j) if u km1+α = for some and (u αk N +m2 , u αk N +m2+r ) = (i -, j -). Using the independence of m 1 and m 2 , we thus obtain

C r i,j = α∈Σ k 1 k ∈G 1 |G| C i-,j-= α∈Σ k 1 k 1 |G| 1 |G| = 1 |G| 2 ,
since we already know by Corollary 2 that for any (i,

j) ∈ G 2 , ∈G C i-,j-= 1 |G| .
More formally, let us introduce the following notations, for any i, j, ∈ G,

A α (N ) = card{m ∈ 0, k N -1 : u km+α = } B r,α i,j (N ) = card{m ∈ 0, k N -r -1 : δ r i,j (α k N + m) = 1}.
We claim that for any α ∈ Σ k , lim

N →∞ A α (N ) k N = 1 |G| , and lim N →∞ ∈G B r,α i-,j-(N ) k N = 1 |G| .
For the first limit, we use the same tools as for Proposition 2. Let φ be the primitive morphism given in Remark 1, so that the sequence u is the image of φ ω (q 0 ) by τ . One can see that the sequence (u kn+α ) n∈N is the image of φ ω (q 0 ) by the function τ : Q → G defined by τ (g, i) = g + f (i, α). As we have already seen in the proof of Proposition 2, all the elements of Q have the same frequency in φ ω (q 0 ). Consequently, each element of G has the same frequency in the image of φ ω (q 0 ) by τ . Indeed, for any g ∈ G and i ∈ Σ k , there exists exactly one g ∈ G such that τ (g, i) = g , so that the cardinal of τ -1 ({g }) does not depend on the choice of g .

For the second limit, observe that lim

N →∞ ∈G B r,α i-,j-(N ) k N = lim N →∞ ∈G (αk N + k N -r) • C r i-,j-(αk N + k N -r) -αk N • C r i-,j-(αk N ) k N = ∈G (α + 1) • C r i-,j--α • C r i-,j- = 1 |G| .
Now, for any (i, j) ∈ G 2 , we have

k 2N +1 -1 n=0 δ r i,j (n) ≥ α∈Σ k ∈G A N (α) B N i-,j-(α).
It follows that

C r i,j (k 2N +1 ) ≥ 1 k α∈Σ k ∈G A N (α) k N B N i-,j-(α) k N .
When N goes to infinity, we know that the limit of the left term exists and is equal to C r i,j . We thus obtain

C r i,j ≥ 1 |G| 2 .
Since (i,j)∈G 2 C r i,j = 1, this ends the proof.

Higher dimensional generalized Golay-Shapiro sequences

We propose the following natural extension of Def. 1 and 3 in dimension d. For greater readability, we represent the elements of Σ d k as column vectors.

x d i    ,    x 1 i+1 . . . x d i+1       = i∈N f (x i , x i+1 ), where x = (x i ) i∈N =    x 1 . . . x d    =    (x 1 i ) i∈N . . . (x d i ) i∈N    =    [n 1 ] k . . . [n d ] k   .
We say furthermore that the sequence u is a generalized d-dimensional Golay-Shapiro sequence if the function f satisfies, for every (i, j) ∈ Σ d k × Σ d k with i = j, and for every g ∈ G,

card h ∈ Σ d k : f (i, h) -f (j, h) = g = k d |G| .
Equivalently, this amounts to saying that the matrix (f (i, j)

) (i,j)∈Σ d k ×Σ d k is a difference matrix.
The definition above can be extended to d-dimensional sequences for which the base k i may depend on the component i ∈ {1, . . . , d} (in the difference condition, k d is then replaced by the product k 1 . . . k d ). However, for simplicity, we restrict ourselves to the case of a unique base k.

Let r ∈ N d \ {(0, . . . , 0)}. For n = (n 1 , . . . , n d ) ∈ N d , we introduce the representations of n and n + r in base k as follows

[n] k = x =    x 1 . . . x d    , [n + r] k = y =    y 1 . . . y d    ,
and we define the integer c n = min{i ∈ N : x j = y j for all j > i}, which measures how far the carry propagates when adding r to n. We define again the fibre of n as the set

F r (n) = {m ∈ N : x = [m] k satisfies x i = x i for every i ∈ N \ {c n + 1}},
and use the notation ∆ r (n) = u n+r -u n .

Since the d-dimensional sequence has d components that are all 1-dimensional and independent, the previous arguments can be repeated verbatim. Proposition 6. If u is a generalized d-dimensional Golay-Shapiro sequence, then for any n ∈ N, and any g ∈ G, we have

card{m ∈ F r (n) : ∆ r (m) = g} = π.
The following table gives the first values of u n1,n2 , for (n 1 , n 2 ) ∈ 0, 2 3 -1 2 . 7

1 0 1 0 0 1 0 1 6 0 0 1 1 1 1 0 0 Concerning the second example (second part of Figure 1), it can be seen that the weight function satisfies

5 1 1 1 1 1 1 1 1 4 0 1 1 0 0 1 1 0 3 1 0 0 1 0 1 1 0 2 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 n2 n1 0
f i 1 i 2 , j 1 j 2 ≡ i 1 1 + i 2 j 2 (mod 2).
As a consequence, the sequence obtained can also be computed by u m,n = v m + v n , where v is the classical one-dimensional Golay-Shapiro sequence.

5 Extensions and open questions 5.1 Block-additive sequences of rank larger than 2

Until now, we have only considered block-additive functions of rank 2. More generally, we can consider the notion of block-additive functions of rank L, for an integer L ≥ 1, in the sense of Cateland [START_REF] Cateland | Digital sequences and k-regular sequences[END_REF].

Definition 5. Let (G, +) be a finite abelian group, let k ∈ N \ {0}, and for an integer L ≥ 1, let f : Σ L k → G be a function satisfying f (0, 0, . . . , 0) = 0. We say that the sequence u = (u n ) n∈N ∈ G N is a block-additive sequence (of rank L) in base k of weight function f if for any integer n ∈ N, we have

u n = i∈N f (x i , x i+1 , . . . , x i+L-1 ), where [n] k = x.
Let (G, +) be a finite abelian group, and let k ∈ N \ {0}. For an integer L ≥ 2, we say that the function d : Σ L k → G satisfies the difference condition (of rank L) if for every (i, j) ∈ Σ k × Σ k with i = j, for every (x 2 , . . . , x L-1 ) ∈ Σ L-2 k , and for every g ∈ G,

card{h ∈ Σ k : d(i, x 2 , . . . , x L-1 , h) -d(j, x 2 , . . . , x L-1 , h) = g} = k |G| .
The difference condition is a sufficient condition for obtaining the same results as in Section 3, for block-additive sequences of rank L with L ≥ 2. This function satisfies the difference condition. Consequently, the block-additive sequence u = (u n ) n∈N of weight function f , which is such that u n counts (modulo 2) the number of blocks different from 000 and 111 in the binary representation of n, has the same correlations of order 2 as a binary sequence chosen uniformly at random.

Open question 1. How can we generate functions satisfying the difference condition of rank L? Could there be a weaker condition on the weight function for which the block-additive sequences obtained would have the same correlations of order 2?

5.2 Can an automatic sequence look even more random?

Another possible direction of research consists in trying to construct blockadditive sequences for which not only the correlations of order 2, but also correlations of higher order would be the same as for uniform random sequences. Precisely, for integers 0 < r 1 < • • • < r -1 , and for a choice (i 0 , . . . , i -1 ) ∈ G , we introduce δ r i0,...,i -1 (n) = 1 if (u n , u n+r1 , . . . , u n+r -1 ) = (i 0 , . . . , i -1 ), 0 otherwise, and we look at the asymptotic behaviour of 1 N N -1 n=0 δ r i0,...,i -1 (n), when N goes to infinity. We say that a sequence has the same correlations of order as a uniform random sequence if for any choice of 0 < r 1 < • • • < r -1 , and for any (i 0 , . . . , i -1 ) ∈ G , lim

N →∞ 1 N N -1 n=0 δ r i0,...,i -1 (n) = 1 |G| .
Open question 2. For a given ≥ 3, is it possible to construct a block-additive sequence having the same correlations of order as a uniform random sequence? Note that it is not possible to construct an automatic sequence such that for every ≥ 1, the correlations of order would be the same as for a uniform random sequence. Indeed, this would in particular imply the sequence to be normal, while the complexity of an automatic sequence is at most linear.

Example 3 .

 3 We represent below the DFAO given by the proof of Proposition 1 for the (classical) Golay-Shapiro sequence.

Definition 4 .

 4 Let (G, +) be a finite abelian group, and let k ∈ N \ {0}. We say that the sequence u= (u n1,...,n d ) (n1,...,n d )∈N d ∈ G N d is a d-dimensional blockadditive sequence in base k if there exists a map f : Σ d k × Σ d k → G satisfyingf such that for any integer n ∈ N d , we have u n1,...,n d =

1 2 3 4 5 6 7

 7 These values are also contained in the bottom-left 8 × 8-squares of the two pictures that are on the first part of Figure1.

-1 2

 2 Terms in 0, 2 7 -1 2

Figure 1 :-1 2

 12 Figure 1: Examples of generalized 2-dimensional Golay-Shapiro sequences in base 2

Figure 2 : 2 Example 8 .

 228 Figure 2: Examples of generalized 2-dimensional Golay-Shapiro sequences in base 2

Golay-Shapiro sequences are often referred to as Rudin-Shapiro sequences. In our paper, we prefer to give credit to the historical timeline of discovery as given by Allouche [1,Remark 1].

Acknowledgement. This work was supported partly by the French PIA project "Lorraine Université d'Excellence", reference ANR-15-IDEX-04-LUE, and by the projects ANR-18-CE40-0018 (EST) and ANR-20-CE91-0006 (ArithRand).

We also extend the notations δ r and C r to d-dimensional sequences. Precisely, for N = (N 1 , . . . , N d ), we define

where the notation n < N means that for all i ∈ {1, . . . , d}, n i < N i . We also introduce

Following the previous lines, one can show as in the one-dimensional case that if u is a generalized d-dimensional Golay-Shapiro sequence, then for any

which also allows to obtain the following extension of Proposition 5.

Example 7. In Figures 1 and2, we present four different examples of generalized Golay-Shapiro sequences, for d = 2, k = 2, G = Z 2 . For each example, the values of the function f : Σ 2 2 → Z 2 is given by a matrix, with the elements of Σ 2 2 sorted in the lexicographic order. On the first line of the matrix, one can thus read successively

and then on the second line

and so on. On the pictures, the cell (n 1 , n 2 ) ∈ N 2 is colored in blue if u n1,n2 = 1 and in white if u n1,n2 = 0. The corner corresponding to the value u 0,0 is the bottom-left corner.

Let us present in more detail the first example. For i, j ∈ Σ 2 2 , the weight function satisfies f (i, j) = 0 if i = j, and f (i, j) = 1 otherwise. As an example, we compute below u 436,48 .

[436] 2 = 0 0 1 0 1 1 0 1 1 0 0 • • • [48] 2 = 0 0 0 0 1 1 0 0 0 0 0 • • • u 436,48 ≡ 0 + 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1 + 0 + • • • ≡ 0 (mod 2)


Hajime Kaneko

-Thomas Stoll

PRODUCTS OF INTEGERS WITH FEW NONZERO DIGITS

Let s(n) be the number of nonzero bits in the binary digital expansion of the integer n. We study, for fixed k, , m, the Diophantine system

and s(b) = m, in odd integer variables a, b. When k = 2 or k = 3, we establish a bound on ab in terms of and m. While such a bound does not exist in the case of k = 4, we give an upper bound for min{a, b} in terms of and m.

Introduction

The multiplicative structure of integers and their digital representation seem to be unrelated in many aspects. In recent years a number of results have been obtained with respect to this phenomenon via a study of distribution properties (distribution mod 1, distribution in arithmetic progressions etc.), see in particular [START_REF] Martin | Propriétés locales des chiffres des nombres premiers[END_REF][START_REF] Mauduit | Sur un problème de Gelfond: la somme des chiffres des nombres premiers[END_REF] and their extensive lists of references for the distribution properties of the digits of primes. Only very few results are known that relate in a concrete way the digital structure of integers to their multiplicative decomposition. This is mainly due to the difficulty of following the multiple carry propagations in 2010 M a t h e m a t i c s S u b j e c t C l a s s i f i c a t i o n: 11A63 (primary), and 11B83 (secondary). K e y w o r d s: sum of digits; digital expansion; factors. The first author is supported by JSPS KAKENHI Grant Number 19K03439. The second author is supported by the French PIA project "Lorraine Université d'Excellence", reference ANR-15-IDEX-04-LUE, and by the projects ANR-18-CE40-0018 (EST) and ANR-20-CE91-0006 (ArithRand).

additions and multiplications. The aim of the present paper is to investigate via a combinatorial approach the relationship of the binary sum of digits function, i.e. the bits-counting function, of products of integers to those of its factors.

For a positive integer n, let s(n) denote the number of nonzero digits in the binary expansion of n (e.g., s(23) = s((10111) 2 ) = 4). We are interested in the Diophantine system with odd integer variables a, b, s(ab) = k, s(a) = , and s(b

) = m, (1)
where k, , m ≥ 2 are arbitrary but fixed integers. Natural questions are the following: If k is fixed, are a and b bounded in terms of and m? If yes, what would such bounds look like?

Since s(ab) ≤ s(a)s(b) for all integers a, b (carry propagations can only cancel out nonzero bits but never create additional ones), it is immediate that we need k ≤ m as a necessary condition for the existence of solutions in [START_REF] Bennett | Perfect powers with three digits[END_REF]. However, it is far from clear for which triples (k, , m) such solutions exist, or even more generally, whether there are finitely of infinitely many solutions in odd a, b for the system (1) for a given triple (k, , m). Part of the motivation to study (1) also comes from a paper of Hare, Laishram, Stoll [START_REF] Hare | The sum of digits of n and n 2[END_REF] where the authors studied the solution set of the equation s(a 2 ) = s(a) = k, which is a particular instance of (1). For example, they showed that s(a 2 ) = s(a) = 8 only allows finitely many odd solutions a, whereas s(a 2 ) = s(a) = 12 has infinitely many odd solutions a. Note also, that due to a classical result of Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF], we have lim inf a→∞ s(a 2 )/s(a) = 0, so that it may not be too rare to have integers a such that a 2 has a much lower number of nonzero bits than the integer a itself (the results holds true also for higher powers and in a more general context, see [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF][START_REF] Madritsch | On simultaneous digital expansions of polynomial values[END_REF][START_REF] Mei | The sum of digits of polynomial values[END_REF][START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF][START_REF] Saunders | Sums of digits in q-ary expansions[END_REF]). Before going any further, let us first mention several related results for the nonzero bits of powers of integers from the literature that we will translate into our language.

A direct elementary calculation shows that s(a 2 ) = 2 implies a = 3. Larger values already demand more sophisticated tools. Szalay [START_REF] Szalay | The equations 2 n ±2 m ±2 l = z 2 , Indag[END_REF] showed that the only solutions of s(a 2 ) = 3 are a = 2 n + 1 (n ≥ 1), a = 7 and a = 23, and his proof is based on a deep result of Beukers [START_REF] Beukers | On the generalized Ramanujan-Nagell equation I[END_REF] on the generalized Ramanujan-Nagell equation. Various other results are known for other powers of integers. We mention in particular the results of Corvaja and Zannier [START_REF] Corvaja | Finiteness of odd perfect powers with four nonzero binary digits[END_REF], and Bennett, Bugeaud and Mignotte [START_REF] Bennett | Perfect powers with few binary digits and related Diophantine problems[END_REF], who showed that for all d there are only finitely many solutions of s(a d ) = 4 and that for all d ≥ 5 the equation s(a d ) = 4 has no solution. The proofs are based on the Subspace Theorem, linear forms in logarithms and Padé approximations. To get an idea about the difficulty of these innocent looking problems, let us mention that there is so far no method at disposal to decide whether the only odd solutions of s(a 2 ) = 4 are a = 13, 15, 47, 111. For more on the problem of powers of few nonzero digits, see [START_REF] Bennett | Perfect powers with three digits[END_REF][START_REF] Bennett | Perfect powers with few binary digits and related Diophantine problems II[END_REF][START_REF] Luca | The Diophantine equation x 2 = p a ± p b + 1[END_REF] and the references given therein. For a result on the digits of smooth numbers, see [START_REF] Bugeaud | On the digital representation of smooth numbers[END_REF]. The occurrence of an additional variable b in (1) adds more freedom and more possible solutions.

The system (1), for k = 2, can also be seen as an investigation of the digits of the factors of the famous Fermat numbers 2 n + 1. These are exactly those integers n with s(n) = 2, so writing n = ab and considering (1) leads to the question of the digital expansion of the factors of Fermat numbers. The problem to factorize 2 n + 1 is a notorious difficult and classical problem in computational number theory (see Brillhart, Lehmer, Selfridge [START_REF] Brillhart | New primality criteria and factorizations of 2 m ± 1[END_REF]) and the size of the largest prime factor is of considerable interest in number theory, too (see Stewart [START_REF] Stewart | On divisors of Fermat, Fibonacci, Lucas, and Lehmer numbers[END_REF]). The well-known, still widely open question concerning Fermat numbers is to know whether s(p) = 2 has infinitely many solutions in primes p.

In the present paper we tackle the cases k = 2, 3, 4 for the system (1). In particular, we show that for k = 2, 3 the system (1) only has finitely many (in principle, effectively computable) solutions for fixed and m, while the situation changes for k = 4.

The structure of the paper is as follows. In Section 2 we state our main results. We then proceed directly to the proofs (Sections 3, 4, 5 and 6). Our combinatorial key lemma appears in Section 3, it will be exploited in several ways throughout the paper.

Main results

Our first main result deals with the case k = 2 for (1). (

) 2
An analogous result to Theorems 2.1 and 2.2 does not hold for the case of s(ab) = 4. In fact, we have the following: While it is not possible to bound the product ab in this case, we can still bound min{a, b} in terms of s(a) and s(b).

Key lemma and proof of Theorem 2.1

The following is our key lemma that we will use throughout the paper. Lemma 3.1. Let Λ be a nonempty finite set. For each n ∈ Λ, let c n be a nonnegative integer. Suppose that

s n∈Λ 2 cn = 1.
Then, for all n, m ∈ Λ, we have

|c n -c m | ≤ max{0, -2 + Card Λ},
where Card denotes the cardinality. P r o o f. Suppose Card Λ ≥ 2 and let c = min n c n and c = max n c n . If there were only one n such that c = c n then s n∈Λ 2 cn ≥ 2 since the term 2 c contributes to the sum with one bit and all the other terms at least with one bit, which is impossible. This means that, in order to have s n∈Λ 2 cn = 1, the term 2 c has to generate a carry that is transported as far as to interact with 2 c . This directly implies the bound (which is sharp in this general setting).

We now turn to the proof of Theorem 2.1. Recall that m, ≥ 2. Put

a = -1 i=0 2 ai , b = m-1 j=0 2 bj , where a -1 > • • • > a 1 > a 0 = 0, and b m-1 > • • • > b 1 > b 0 = 0. By s(ab) = 2,
we see that ab can be written as

ab = 2 x + 1,
for some x > 0. Since carry propagation goes from the lower to the higher significant digits, we observe that a 1 = b 1 since otherwise we would end up with at least three binary digits. Put

Λ = {(i, j) | 0 ≤ i ≤ -1, 0 ≤ j ≤ m -1, (i, j) = (0, 0)} .
Since Card Λ ≥ 2 we can apply Lemma 3.1 with

c (i,j) = a i + b j to get 0 < (a -1 + b m-1 ) -(a 1 + 0) ≤ -2 + Card Λ = -3 + m. (3)
Similarly,

0 ≤ (a -1 + b m-1 ) -(a 1 + a 1 ) ≤ -3 + m. (4)
Therefore, by ( 3) and ( 4),

2a 1 ≤ a -1 + b m-1 ≤ a 1 -3 + m,
and so a 1 ≤ -3 + m.

Using (3) again, we obtain

a -1 + b m-1 ≤ a 1 -3 + m ≤ -6 + 2 m.
Since a < 2 1+a -1 and b < 2 1+bm-1 , we deduce that

ab < 2 2+a -1 +bm-1 ≤ 2 -4+2 m ,
which finishes the proof of Theorem 2.1.

Proof of Theorem 2.2

As before, we put

a = -1 i=0 2 ai , b = m-1 j=0 2 bj , where a -1 > • • • > a 1 > a 0 = 0, and b m-1 > • • • > b 1 > b 0 = 0. By s(ab) = 3,
the integer ab can be written as

ab = 2 x + 2 y + 1,
where x > y > 0.

We now distinguish two cases whether a 1 = b 1 or a 1 = b 1 . The second case is more involved since the carry then cancels out one binary digit and we have to inspect in more detail the possible interactions.

-The case a 1 = b 1 :

First we consider the case of a 1 = b 1 . Without loss of generality, we may assume that a 1 < b 1 . Again, as carries propagate from the lower to the higher significant digits, we have y = a 1 . It is easily seen that ≥ 3. In fact, if = 2, then we have

2 x = 0≤i≤1 1≤j≤m-1 2 ai+bj = (1 + 2 a1 )   1≤j≤m-1 2 bj   , a contradiction. Suppose now ≥ 3. Since 2 x = (i,j) =(0,0),(1,0) 2 ai+bj , applying Lemma 3.1 with Λ = {(i, j) | 0 ≤ i ≤ -1, 0 ≤ j ≤ m -1, (i, j) = (0, 0), (1, 0)} and c (i,j) = a i + b j , we get 0 < (a -1 + b m-1 ) -min{a 2 , b 1 } ≤ -2 + Card Λ = -4 + m.
Thus, we see

2 min{a 2 , b 1 } ≤ a 2 + b 1 ≤ a -1 + b m-1 ≤ min{a 2 , b 1 } -4 + m,
and so min{a 2 , b 1 } ≤ -4 + m and

a -1 + b m-1 ≤ -8 + 2 m.
Thus, we obtain

ab < 2 2+a -1 +bm-1 ≤ 2 -6+2 m < 2 -13+4 m . -The case a 1 = b 1 :
In what follows, we assume that [START_REF] Bennett | Perfect powers with few binary digits and related Diophantine problems[END_REF] in the same way as above. Thus, we may assume that

a 1 = b 1 . If a -1 + b m-1 ≤ a 1 -4 + m, then we get
a -1 + b m-1 ≥ a 1 -3 + m. ( 5
) Let Ξ := {(i, j) | 0 ≤ i ≤ -1, 0 ≤ j ≤ m -1, (i, j) = (0, 0)} . Consider -1 i=0 2 ai   m-1 j=0 2 bj   = 1 + (i,j)∈Ξ 2 ai+bj = 1 + 2 y + 2 x . (6)
By ordering all the sums a i + b j in increasing order (there might be multiple equal terms), we can regroup several (smaller) sums to generate 2 x and all the other ones to generate 2 y . More precisely, there exist nonempty subsets Ξ 1 , Ξ 2 of Ξ satisfying the following:

(i) Ξ = Ξ 1 ∪ Ξ 2 is a disjoint union.
(ii)

2 y = (i,j)∈Ξ1 2 ai+bj , 2 x = (i,j)∈Ξ2 2 ai+bj .
Note that this decomposition is in general not unique and that Card Ξ k ≤ -2 + m for k = 1, 2. Using Lemma 3.1, we see for k = 1, 2 that

|(a i + b j ) -(a i + b j )| ≤ max{0, -2 + Card Ξ k } ≤ -4 + m (7)
for all (i, j), (i , j ) ∈ Ξ k . In particular, (5) implies that

( -1, m -1) ∈ Ξ 2 , (1, 0), (0, 1) ∈ Ξ 1 .
Now we add further assumptions on Ξ 1 and Ξ 2 . In the case of y ≥ a 1 + b 1 , and if necessary by changing the order of terms in (6), we may assume that (1, 1) ∈ Ξ 1 .

In either case we therefore have (and note, for further reference)

y < a 1 + b 1 or (1, 1) ∈ Ξ 1 . (8)
In what follows, we consider the following three cases:

• Case 1: (i 0 , 0) ∈ Ξ 2 for some 2 ≤ i 0 ≤ -1.
• Case 2: (0, j 0 ) ∈ Ξ 2 for some 2 ≤ j 0 ≤ m -1.

• Case 3: (i, 0) ∈ Ξ 1 for all 1 ≤ i ≤ -1 and (0, j) ∈ Ξ 1 for all 1 ≤ j ≤ m-1.

We first consider Case 1. Using (7), we have

a i0 + b m-1 ≤ a -1 + b m-1 ≤ a i0 -4 + m,
and so

-4 + m ≥ b m-1 ≥ b 1 = a 1 , 2 -3+ m > b. (9)
We divide the set A := {a i | 1 ≤ i ≤ -1} as follows:

A 1 := {a i | a i ≤ a 1 -4 + m} = {a 1 < a 2 < • • • < a τ }, A 2 := {a i | a i > a 1 -4 + m} = {a 1+τ < • • • < a -1 }.
Note that by [START_REF] Corvaja | Finiteness of odd perfect powers with four nonzero binary digits[END_REF],

a τ -a 1 ≤ -4 + m. ( 10
)
If A 2 is empty, then we have τ = -1. Thus, we see that

a < 2 1+a -1 ≤ 2 1+a1-4+ m ≤ 2 -7+2 m
by ( 9) and ( 10), which implies ab < 2 -10+3 m < 2 -13+4 m . Suppose now that A 2 is not empty. Using ( 7) again, we see

{(i, 0) | τ + 1 ≤ i ≤ -1} ∩ Ξ 1 = ∅,
and so

{(i, 0) | τ + 1 ≤ i ≤ -1} ⊂ Ξ 2 .
In particular, again by [START_REF] Corvaja | Finiteness of odd perfect powers with four nonzero binary digits[END_REF],

a -1 + b m-1 -a 1+τ ≤ -4 + m. (11)
We claim that

a 1+τ -a τ ≤ -3 + m. (12)
Suppose on the contrary that a 1+τ -a τ ≥ -2 + m. Let

a := τ i=0 2 ai , a := -1 i=τ +1
2 ai-a1+τ .

We observe that ab = a b + a b2 a1+τ

and by [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF],

a b < 2 1+aτ • 2 -3+ m = 2 -2+ m+aτ ≤ 2 a1+τ .
Therefore, since s(b) ≥ 2, we get s(ab) = s(a b) + s(a b) ≥ 2 + 2 = 4, a contradiction. Hence, we proved [START_REF] Martin | Propriétés locales des chiffres des nombres premiers[END_REF]. We combine now ( 9), ( 10), [START_REF] Martin | Propriétés locales des chiffres des nombres premiers[END_REF], and [START_REF] Madritsch | On simultaneous digital expansions of polynomial values[END_REF] and deduce that

a -1 + b m-1 = a 1 + (a τ -a 1 ) + (a τ +1 -a τ ) + (a -1 + b m-1 -a 1+τ ) ≤ (-4 + m) + (-4 + m) + (-3 + m) + (-4 + m) = -15 + 4 m, which implies (2).
In the same way as above, we can prove (2) in Case 2.

In what follows, we consider Case 3. We recall [START_REF] Hare | The sum of digits of n and n 2[END_REF]. First, we suppose y < a 1 + b 1 . Then we see that for all 1 ≤ i ≤ -1 and 1 ≤ j ≤ m -1 that (i, j) ∈ Ξ 1 by y < a i + b j . Hence,

Ξ 1 = {(i, 0) | 1 ≤ i ≤ -1} ∪ {(0, j) | 1 ≤ j ≤ m -1}, Ξ 2 = {(i, j) | 1 ≤ i ≤ -1, 1 ≤ j ≤ m -1}.
In particular, we get

2 x = -1 i=1 2 ai   m-1 j=1 2 bj   , which contradicts ( , m) = (2, 2).
Now, suppose (1, 1) ∈ Ξ 1 . Since (1, 1), (1, 0) ∈ Ξ 1 , we get by [START_REF] Corvaja | Finiteness of odd perfect powers with four nonzero binary digits[END_REF] and

a 1 = b 1 that (a 1 + b 1 ) -a 1 = a 1 ≤ -4 + m.
On the other hand, ( -

1, 0), (1, 0) ∈ Ξ 1 implies a -1 ≤ a 1 -4 + m ≤ -8 + 2 m.
In the same way, by using (0, m -1), (1, 0

) ∈ Ξ 1 , we get b m-1 ≤ -8 + 2 m. Hence, we deduce ab < 2 -14+4 m .
This completes the proof of Theorem 2.2. .

Proof of Theorem 2.3

We prove the result via a specific construction (other constructions are possible, too). Put f (X) := X 9 + 1. Observe that

f (X) = (X + 1)(X 2 -X + 1)(X 6 -X 3 + 1) = (X 2 -X + 1)(X 7 + X 6 -X 4 -X 3 + X + 1). ( 13
)
For any positive integer n, set

a 0 = a 0 (n) := 2 2n -2 n + 1, b 0 = b 0 (n) := 2 7n + 2 6n -2 4n -2 3n + 2 n + 1.
By [START_REF] Mauduit | Sur un problème de Gelfond: la somme des chiffres des nombres premiers[END_REF] we have a 0 b 0 = 2 9n + 1. Since s(a 0 ) = n + 1 and s(b 0 ) = 3n + 2 we see that for any positive integer L and n sufficiently large we have

s(a 0 ) ≥ L, s(b 0 ) ≥ L. ( 14
)
We now fix a positive integer n satisfying [START_REF] Mei | The sum of digits of polynomial values[END_REF]. Put := s(a 0 )(≥ L) and m := s(b 0 )(≥ L). For a positive integer N , we set

a (N ) := a 0 , b (N ) := b 0 (2 N + 1) = 2 N b 0 + b 0 .
If N is sufficiently large, depending on and n, then we get

s(a (N ) ) = , s(b (N ) ) = s(2 N b 0 ) + s(b 0 ) = 2s(b 0 ) = 2m =: m.
Moreover,

s(a (N ) b (N ) ) = s((2 N + 1)a 0 b 0 ) = s(2 N +9n + 2 N + 2 9n + 1) = 4.
Hence, we obtain Theorem 2.3.

Proof of Theorem 2.4

The proof of Theorem 2.4 follows the same line of argument as used in Theorems 2.1 and 2.2. We start off again with putting

a = -1 i=0 2 ai , b = m-1 j=0 2 bj , where a -1 > • • • > a 1 > a 0 = 0, and b m-1 > • • • > b 1 > b 0 = 0. By s(ab) = 4,
we see that ab can be written as

ab = 2 x3 + 2 x2 + 2 x1 + 1,
where

x 3 > x 2 > x 1 > 0. Let Ξ := {(i, j) | 0 ≤ i ≤ -1, 0 ≤ j ≤ m -1, (i, j) = (0, 0)} .
Similarly as before, and by considering the carry propagation in the multiplication, we have

-1 i=0 2 ai   m-1 j=0 2 bj   = 2 x3 + 2 x2 + 2 x1 + 1,
and there exist nonempty subsets Ξ k (k = 1, 2, 3) of Ξ satisfying the following:

(i) Ξ = Ξ 1 ∪ Ξ 2 ∪ Ξ 3 is a disjoint union. (ii) 2 x k = (i,j)∈Ξ k 2 ai+bj for k = 1, 2 , 3.
P r o o f. Without loss of generality we may assume that r(a) ≤ r(b). First we consider the case of r(a) = 1. By the inequalities [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF] and by applying Lemma We are now ready to prove Theorem 2.4 by contradiction. Assume that min{a, b} ≥ 2 18 m , and so

a -1 ≥ 18 m, b m-1 ≥ 18 m. (16)
Without loss of generality we may assume that

b m-1 -b 1 ≥ a -1 -a 1 . (17)
We divide the proof of Theorem 2.4 into three cases that will be dealt with in the following three subsections:

• Case 1:

a -1 -a 1 ≤ 4 m, b m-1 -b 1 ≤ 13 m. (18)
• Case 2:

a -1 -a 1 ≤ 4 m, b m-1 -b 1 > 13 m. (19)
• Case 3: Let i, i be any indices with 1 ≤ i, i ≤ -1. Using ( 16) and ( 18), we have

a -1 -a 1 > 4 m. (20
a i ≥ a 1 ≥ a -1 -4 m ≥ 14 m, (21)
a i -a i ≥ -4 m. (22)
Similarly, for any 1 ≤ j, j ≤ m -1,

b j ≥ b 1 ≥ b m-1 -13 m ≥ 5 m, ( 23
) b j -b j ≥ -13 m. (24)
Putting

T 1 := -1 i=1 2 ai + m-1 j=1 2 bj , T 2 := -1 i=1 m-1 j=1
2 ai+bj , we see that ab = 1 + T 1 + T 2 . We claim by Lemma 6.2 that 4 = s(ab) = 1 + s(T 1 ) + s(T 2 ). In fact, let 1 ≤ i, i ≤ -1 and 1 ≤ j ≤ m -1. Then, using ( 22) and ( 23), we get

(a i + b j ) -a i = (a i -a i ) + b j ≥ -4 m + 5 m = m.
Similarly, ( 21) and (24) imply that, for any 1

≤ i ≤ -1 and 1 ≤ j, j ≤ m -1, (a i + b j ) -b j ≥ 14 m -13 m = m.
Hence, we obtain s(T 1 ) + s(T 2 ) = 3. Observing s(T 2 ) ≥ 2 by ≥ 3 and m ≥ 3, we get s(T 1 ) = 1 and s(T 2 ) = 2. By s(T 2 ) = 2 and , m ≥ 3, there exists an integer z ≥ 2 such that T 2 = 2 a1+b1 (1 + 2 z ). In particular, (25)

On the other hand, using s(T 1 ) = 1 and , m ≥ 3, we see that a 1 = b 1 and that one of the following holds:

a 2 = 1 + a 1 and b 2 > 1 + a 1 = 1 + b 1 , or a 2 > 1 + a 1 and b 2 = 1 + a 1 = 1 + b 1 .
This implies

-1 i=1 2 ai-a1 m-1 j=1
2 bj -b1 ≡ 3 (mod 4), which contradicts (25). This finishes the proof of Theorem 2.4 for the setting of the first case.

In the same way as in the previous subsection, we get for any 1 ≤ i, i ≤ -1 that

a i ≥ 14 m, a i -a i ≥ -4 m. (26)
m-1 -b 1 ≤ r(b) • m + (r(b) -1) • 5 m ≤ 3 m + 2 • 5 m = 13 m,
which contradicts [START_REF] Szalay | The equations 2 n ±2 m ±2 l = z 2 , Indag[END_REF]. We now take the maximal integer p with 2 ≤ p ≤ r(b) that satisfies (27). Put

Λ 1 := {j ∈ Z | 1 ≤ j ≤ -1 + κ(b; p)}, Λ 2 := {j ∈ Z | κ(b; p) ≤ j ≤ m -1}.
For any j ∈ Λ 2 and j ∈ Λ 1 , we have

b j -b j ≥ 5 m. (28)
On the other hand, let j, j ∈ Λ 2 . Using r(b) ≤ 3 again, we get

|b j -b j | ≤ (r(b) -1) m + (r(b) -2) • 5 m ≤ 2 m + 5 m = 7 m,
and so

b j -b j ≥ -7 m. (29)
Putting

T 1 := -1 i=1 2 ai + j∈Λ1∪Λ2 2 bj + -1 i=1 j∈Λ1 2 ai+bj , T 2 := -1 i=1 j∈Λ2
2 ai+bj , we have ab = 1 + T 1 + T 2 . We claim by Lemma 6.2 that 4 = s(ab) = 1 + s(T 1 ) + s(T 2 ). Now we fix any indices 1 ≤ i ≤ -1 and j ∈ Λ 2 . First, for any 1 ≤ i ≤ -1, we get by ( 26) and ( 28) that

(a i + b j ) -a i = (a i -a i ) + b j ≥ -4 m + 5 m = m.
we see that ab = 1 + T 1 + T 2 . We claim by Lemma 6.2 that 4 = s(ab) = 1 + s(T 1 ) + s(T 2 ). Now we fix any indices i ∈ Λ 2 and j ∈ Θ 2 . First, for any i ∈ Λ ∪ {0} and 0 ≤ j ≤ m -1, we get by (32) and ( 33) that

(a i + b j ) -(a i + b j ) ≥ 2 m -m = m.
Similarly, for any 0 ≤ i ≤ -1 and j ∈ Θ 1 ∪ {0}, we see by ( 31) and ( 34) that

(a i + b j ) -(a i + b j ) ≥ m.
Hence, we obtain s(T 1 )+s(T 2 ) = 3. On the other hand, applying Lemma 6.1 to (i, 0) with i ∈ Λ 2 and (i , 0) with i ∈ Λ 1 , we get s(T 1 ) ≥ 2 by (33). Consequently, we obtain s(T 1 ) = 2 and s(T 2 ) = 1. In particular, Λ 2 = { -1} and Θ 2 = {m-1} by s(T 2 ) = 1. Setting a :=

+ (2 a -1 + 2 bm-1 + a 2 bm-1 + b 2 a -1 ) + 2 a -1 +bm-1 = 1 + 2 x1 + 2 x2 + 2 x3 , (35)
where 0 < x 1 < x 2 < x 3 . Using Lemma 6.2, we shall prove the following:

     2 x1 = a + b + a b , 2 x2 = 2 a -1 + 2 bm-1 + a 2 bm-1 + b 2 a -1 , 2 x3 = 2 a -1 +bm-1 . (36)
First, we observe that a , 2 a -1 , and 2 a -1 +bm-1 are subsums of 2 x1 , 2 x2 , and 2 x3 in (35), respectively. In fact, for any 1 ≤ i ≤ -2, we get a -1 -a i ≥ m by (33), and (a -1 + b m-1 ) -a -1 = b m-1 ≥ m by (30). Similarly, b and 2 bm-1 are subsums of 2 x1 and 2 x2 in (35), respectively. For the proof of (36), it suffices to show that a 2 bm-1 , b 2 a -1 , and a b are subsums of 2 x2 , 2 x2 , and 2 x1 in (35), respectively. We fix indices i, i with 1 ≤ i, i ≤ -2. Then we note that (a -1 + b m-1 ) -(a i + b m-1 ) = a -1 -a i ≥ m by (33) and that (a i + b m-1 ) -a i = b m-1 + (a i -a i ) ≥ 4 m -m ≥ m by (30) and i, i ∈ Λ 1 (= {1, 2, . . . , -2}). Thus, a 2 bm-1 is a subsum of 2 x2 in (35). In particular, Lemma 6.1 implies for any 1 ≤ i ≤ -2 that

Theorem 2 . 1 .

 21 Let , m ≥ 2 be integers, and a, b ≥ 1 be odd integers with s(a) = and s(b) = m. If s(ab) = 2, then ab < 2 -4+2 m . There is an obvious infinite solution set for k = 3 and = m = 2 for (1), namely, a = b = 2 c + 1 for c ≥ 1. Avoiding this case, we get an analogous result to Theorem 2.1 for k = 3. Theorem 2.2. Let , m ≥ 2 be integers with max{ , m} ≥ 3. Moreover, let a, b ≥ 1 be odd integers with s(a) = and s(b) = m. If s(ab) = 3, then ab < 2 -13+4 m .

Theorem 2 . 3 .

 23 For all integers L ≥ 1 there exist integers , m ≥ L such that there are infinitely many pairs (a, b) of positive odd integers with s(a) = , s(b) = m, and s(ab) = 4.

Theorem 2 . 4 .

 24 Let , m ≥ 3 be integers, and a, b ≥ 1 be odd integers with s(a) = and s(b) = m. If s(ab) = 4, then we have min{a, b} < 2 18 m .

≥ 1 +

 1 6.2 for (0, b κ(b;p) ) (p = 1, 2, . . . , r(b)), we get 4 = s(ab) = 1 + s r(b), and so r(b) ≤ 3. Next, we consider the case of r(a) ≥ 2. Suppose that r(b) ≥ 3. Set y 1 := a κ(a;1) + b κ(b;1) , y 2 := a κ(a;1) + b κ(b;2) , y 3 := a κ(a;2) + b κ(b;2) , y 4 := a κ(a;2) + b κ(b;3) . The inequalities (15) imply for any 2 ≤ p ≤ 4 that y p -y p-1 ≥ m. Thus, we get by Lemma 6.1 that 4 = s(ab) = 1 + s Hence, we obtain 2 = r(b) ≥ r(a) ≥ 2, and so r(a) = r(b) = 2.

) 6 . 1 .

 61 Case 1: a -1 -a 1 ≤ 4 m and b m-1 -b 1 ≤ 13 m

2

  bj -b1 ≡ 1 (mod 4).

We claim that there exists 2 ≤

 2 p ≤ r(b) such that b κ(b;p) -b -1+κ(b;p) > 5 m. (27) Suppose on the contrary that there does not exist 2 ≤ p ≤ r(b) satisfying (27). Since r(b) ≤ 3 by Lemma 6.3, we get b

- 2 i=1 2 2 j=1 2

 2222 ai and b := mbj , we see that ab = 1 + (a + b + a b )

≥ 3 and m ≥ 3 .

 3 a i ≤ m (37)because both of 2 bm-1 and a 2 bm-1 are subsums of2 x2 in (35). Similarly, b 2 a -1 is a subsum of 2 x2 in (35) and b j ≤ m for any 1 ≤ j ≤ m -2. Finally, let 1 ≤ i ≤ -2 and 1 ≤ j ≤ m -2. Then (34) and (37) imply that b m-1 -(a i + b j ) = (b m-1 -b j ) -a i ≥ 2 m -m = m.Hence, a b is a subsum of 2 x1 in (35). This finishes the proof of (On the other hand, using (36) again, we observe thats 2 a -1 + 2 bm-1 + a 2 bm-1 + b 2 a -1 = s (2 x2 ) = 1, which implies that a -1 = b m-1 becausea and b are even. Moreover, 1 = s(2 + a + b ) = s of the following holds: a 1 = 1 and b 1 ≥ 2, or a 1 ≥ 2 and b 1 = 1. 38). This concludes the proof of Theorem 2.4.

Acknowledgement

We would like to thank Prof. Shigeki Akiyama for fruitful discussion.

From Lemma 3.1 we deduce the following two direct facts that we will use in the sequel. Lemma 6.1. Let i, i , j, j be indices with 0 ≤ i, i ≤ -1 and 0 ≤ j, j ≤ m -1. If |(a i + b j ) -(a i + b j )| ≥ m, then (i, j) ∈ Ξ and (i , j ) ∈ Ξ belong to different Ξ k and Ξ k . Lemma 6.2. Let S 1 and S 2 be subsets of Ξ. Assume that, for all (i, j) ∈ S 1 and (i , j ) ∈ S 2 , we have

We shall define the partition Suppose that κ(a; j) and S(a; j) (j = 1, 2, . . . , p) are defined. If S(a) = ∪ 1≤j≤p S(a; j), then the process is terminated and we put r(a) := p. Otherwise, we denote the minimal element of S(a)\(∪ 1≤j≤p S(a; j)) by a κ(a;p+1) . Let

The process ends in at most steps. In fact, for any 1 ≤ p ≤ r(a) the set S(a; p) is not empty since a κ(a;p) ∈ S(a; p). Similarly, we define κ(b; j) ∈ N and S(b; j) ⊂ S(b) for j = 1, 2, . . . , r(b). For all 1 < p ≤ r(a) and 1 < q ≤ r(b), we have

The next lemma shows that the conditions on s(ab) restricts the possible values of (r(a), r(b)) to a small set. Similarly, ( 26) and (29) imply that, for any j

Moreover, if 1 ≤ i ≤ -1 and j ∈ Λ 1 , then ( 26) and (28) imply that

Hence, we obtain s(T 1 ) + s(T 2 ) = 3. On the other hand, we have s(T 2 ) ≥ 2 by ≥ 3. Moreover, applying Lemma 6.1 to (0, j) with j ∈ Λ 2 and (0, j ) with j ∈ Λ 1 , we see that s(T 1 ) ≥ 2 by (28), a contradiction. Hence, we verified the second case.

and so r(a) ≥ 2, r(b) ≥ 2. Lemma 6.3 implies r(a) = r(b) = 2. For 1 ≤ p ≤ 2, we set

Observe that, for any i ∈ Λ 2 and 0 ≤ i ≤ -1,

Similarly, if j ∈ Θ 2 and 0 ≤ j ≤ m -1, then

Moreover, for any i ∈ Λ 2 and i ∈ Λ 1 ∪ {0}, we see that


Characteristics of Human Resources Management In Tourism Industry

Keywords: Tourism, Human Resources Management, Personnel Management, Tourism And Hospitality Industry, Training

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

O identify the features of human resources management in the Republic of Armenia have been prepared a questionnaire to collect information and make an assessment on the mechanism of action and effectiveness of human resources management in tourism enterprises.

The survey of the human resources management in the tourism sector was conducted based on a questionnaire and was completed through personal interviews.

The interviews with HR managers and the representatives of selected tour operators and travel agencies, hotels, restaurants were conducted between May 1-20, 2015 and lasted between 45 minutes to 1 hour.

Detailed interviews were conducted with 20 entities, 10

Koryun Atoyan Professor, Rector of University, Doctor of Sciences, Armenian State University of Economics, Yerevan, Armenia hotels, 6 tour agencies, and 4 restaurants and complemented with analysis of the current situation in the Armenian tourism sector from other research and survey findings. (Only locally owned establishments were included in the sample).

II. SURVEY RESULTS

Results of the survey were analyzed using the SPSS statistical software and MS Excel. The survey revealed that the structure of the human resources management functions performed by the companies is not effective. The functions of job analysis and development of job descriptions, implementation of human resources policy, procedures and systems, and performance appraisal are not accomplished by the majority of companies, or it is common functions between HR manager and another managers.

Analyze of Main Directions of Personnel Management in Tourism Organizations of Armenia

The results showed that the share of employees at the hotels and restaurants made up more than 90% of the total number of the employed at the observed companies. Q1: How many people are working at your company (registered and unregistered). including part-time staff: And the analysis showed the percentage: Job Analysis: is a systematic exploration of the activities within a job.

It defines and documents the duties, responsibilities and accountabilities of a job and the conditions under which a job is performed.

Job Descriptions: Written statement of what jobholder does, how it is done, under what conditions and why. Used to describe the job to applicants, to guide new employees, and to evaluate employees. Around 35% of respondents report that their company does not have written descriptions of their responsibilities, or job descriptions. Only one company reported on job analysis before designing job description. The overwhelming majority of respondents (65%) that they use job descriptions from the existing Employees Qualification directory.

Recruitment and Selection of Employees:

Recruitment is defined by Heery and Noon (2001: 298) as 'the process of generating a pool of candidates from which to select the appropriate person to fill a job vacancy'.

Recruitment is a dynamic process as within organizations people are constantly retiring, resigning, being promoted or, at times, being dismissed. Most HR managers during the interviews said (particularly the large hotels) they use formal methods such as employment and career centers, and use databases of resume, recommendations, word of mouth, as well as publish or follow the announcements in newspapers, journals and Internet. Other methods which organizations may use include performance standards and, matching performance against job descriptions, rating an employee based on a scale, which may for example range from 'outstanding' to 'unacceptable' and critical incidents.

The survey showed that the appraisal system for the evaluation of employee performance is not available at nearly 80% of companies. In hotels they use alternation ranking method (ranking of the employees with best and worst performance). And all companies reported that the supervisors monitor the performance of workers directly and sends a report by the supervisor to the manager hr manager executive manager.

Payment Rewarding/Incentive Systems: Q22 WHAT PAYMENT SYSTEM ARE USED? Q23 Do you have pay increases linked to employee's performance?

Q24 what Rewarding/ Incentive Systems are used? Concerning to the payment all companies use standard hour plan payment. And, for rewarding system most of the observed companies use the pay increases. The most popular types of rewarding systems are bonuses system and regular salary rise, compensation of personal (transportation, food) expenses In addition to the upgrade( in hotels).plus the non-financial rewards at work in all companies .the direct relationship between the managers and the employees. One of the important functions of human resources management is development of short-term and long-term staff training programs. Analyzing training needs is a crucial part of HRD as the identification of needed skills and active management of employee learning is integral to developing corporate, and business strategies.

Training and development then can be seen as a key instrument in the implementation of HRM practices and policies and there may be a number of benefits from undertaking training. For example, McKenna and Beech (2002)

III. CONCLUSION

Armenia is ranked 71st out of 141 countries in terms of quality of human resources ,except if structure of human resource management functions currently performed by companies in tourism sector is not effective and needs improvement through the provision of the advisory services or trainings to enhance the ability of this administration to function independently [2].

Job analysis as the important prerequisite for the elaboration of job descriptions is not practiced at the observed companies. At the same time, performance appraisal practice is very limited and done roughly, mainly based on qualitative indicators. From this point the foreign experience on the peculiarities of job analysis and performance appraisal in tourism sector can be useful for the companies [START_REF] Nickson | Human Resource Management for the Hospitality and Tourism Industries[END_REF].

The submission of the advisory services or organization of training courses on labor legislation, labor code, its specifics for the services sector and private companies along with the observation of the international experience on labor legislation can be very helpful for the tourism companies.

Development of cluster relationships between the companies and educational establishments specialized in tourism field needs to be one of the most important directions of tourism development in the country.

The survey results showed that the highest training needs of respondents are concentrated on HRM general skills, job analysis skills and the absence of job analysis from HR functions reflect the importance of training courses for human management managers in this field.

On general skills side the highest training needs are registered on entrepreneurial and marketing, customer care skills, as well as on restaurant management/operation skills [START_REF]Tourism and Hospitality Marketing[END_REF].

Encourage the internal tourism by give low praises for the local Armenians this enhance the internal tourism.

Fig 1 .

 1 Fig 1. Analyzed Functions Performed By Human Management Department Generally recruiting and selecting people to fill new or existing positions are a crucial element of human resource activity in all tourism and hospitality organizations, irrespective of size, structure or activity. Although we have noted how the importance of service quality has increased the pressure on organizations to select the 'right' kind of individual, (figure number 1) Showed that the recruitment and selection of employees the most important function among HR function 25% , and training 20%.while the performance appraisal 13% .and the labor relation only 3%. Job Analysis and job description

Q20

  Do u have an appraisal system for the evaluation of employee performance? Q21 If yes, what methodologies of appraisal of employees performance are used? Performance appraisal is defined by Heery, and Noon (2001: 7) as,' the process of evaluating the performance and assessing the development/training needs of an employee'. Performance appraisal can arguably be seen to again reflect to some degree the notions of and 'soft' HRM. IDS (1989, cited in McKenna and Beech, 2002) suggest a number of performance factors which are likely to be appraised, the most important being: • Knowledge, ability and skill on the job. • Attitude to work expressed as enthusiasm, commitment and motivation. • Quality of work on a consistent basis and attention to detail. • Volume of productive output. • Interaction, as exemplified in communication skills and ability to relate to others in teams. Woods et al. (1998) found that hotels in their survey used one or more of four approaches, these being management by objective (MBO) (48 per cent), behaviorally anchored rating scales (BARS) (41 per cent), and narrative essay (37 per cent) and graphic rating scale (28 per cent).

Fig. 2

 2 Fig. 2 Type of payment Rewarding/ Incentive Systems

TABLE IV WRITTEN

 IV STATEMENT OF WHAT JOBHOLDER DOES

TABLE V

 V

			JOB DESCRIPTION
			FREQUENCY	PERCENT
	YES		1	5%
	NO		6	30%
	We use job descriptions	13	65%
	from	employees
	Qualifications directory
	Total		20	100

TABLE VI

 VI

		. METHODS FOE SELECT EMPLOYEE
		Type	frequency	%
	1	Apply to colleagues or other employers	12	18.46154
	2	Apply to relatives and acquaintances	2	3.076923
	3	Publish or follow the announcements	12	18.46154
		(newspapers, journals, Internet and
		others)
	4	Partner universities/institutions	8	12.30769
	5	Non-partner higher educational/training
		institutions


On the largest prime factors of consecutive integers in short intervals

Zhiwei Wang *

Introduction

For each integer n 1, let P (n) denote the largest prime factor of n with the convention that P (1) = 1. In 1930, Dickman [START_REF] Dickman | On the frequency of numbers containing prime factors of a certain relative magnitude[END_REF] obtained the well-known result: the following asymptotic formula Ψ(x, y) = |{n x : P (n) y}| ∼ x (u) (u 1) (

holds for x → ∞ with u = log x/ log y fixed, where (u) is the Dickman function. Furthermore, one conjectured that the largest prime factors of consecutive integers n and n + 1 are "independent events", that is to say, the density of integers n with P (n) < P (n + 1) is 1/2. In this direction, in 1978 Erdős and Pomerance [START_REF] Erdös | On the largest prime factors of n and n + 1[END_REF] proved that there exists a positive proportion of integers n with P (n) < P (n + 1). More precisely, they proved that Theorem (A). For x → ∞, we have |{n x : P (n) < P (n + 1)}| > 0.0099x.

Another important problem on consecutive integers is the following. Let {ε n } 1 n<N be a finite sequence with each ε n ∈ {0, ±1}, and write

a b = 1 n<N n n + 1 εn ,
where the fraction is in its smallest terms, then define A(N ) as the maximal value of a as {ε n } 1 n<N runs through all possible 3 N -1 sequences of 0, ±1. In 1988, Nicolas [START_REF] Nicolas | Nombres hautement composés[END_REF] showed that log A(N ) In 2005, La Bretèche, Pomerance and Tenenbaum [START_REF] De La Bretèche | Products of ratios of consecutive integers[END_REF] improved the lower bound of log A(N ) to the same order of magnitude as the upper bound:

Theorem (B). For large N , we have

log A(N ) {K + o(1)}N log N, (1.2)
where K ≈ 0.107005 is a constant.

Further, they proved that for any fixed c 0 ∈ [0, 1 5 ) and uniformly for c

∈ [0, c 0 ], x → ∞, S(x, c) 2x c 0 log 1 -v 1 -v -2c dv 1 -v + o(x), (1.3)
where S(x, c) denotes the number of those integers n not exceeding x such that P (n) > x 1-c and P (n + 1) > x 1-c . In fact, (1.2) is an easy consequence of (1.3). Besides, from (1.3) they also improved the result of Theorem (A) and obtained Theorem (C). For x → ∞, we have

|{n x : P (n) < P (n + 1)}| > 0.05544x.
In addition, in their paper they also indicated that the constant 0.05544 can be improved to 0.05866 by using more sophisticated sieve methods thanks to an observation of Fouvry. Indeed, when using sieve methods, La Bretèche, Pomerance and Tenenbaum disposed the sum of error term by the Bombieri-Vinogradov theorem, while Fouvry used a type of convolution of the Bombieri-Vinogradov theorem, which can improve the distribution level leading an improvement of the constant.

In this paper, we consider the largest prime factors of consecutive integers in short intervals (x, x + y] with y = x θ with 3 5 < θ 1. Throughout this paper, we denote by ε an arbitrarily small positive constant, γ Euler's constant and p, p primes. For convenience, we write L = log x.

Our results are as follows.

Theorem 1. (i) Let (1.4)

Then for x → ∞ and y = x θ , we have

{x < n x + y : P (n) < P (n + 1)} {g(θ; c) + o θ,c (1)}y, (1.5)
where

g(θ; c) := log 1 1 -c -2 c 0 log(1 -v) -1 θ -1 2 -v dv. (1.6) (ii) For 3 5 < θ 1, there is a unique c(θ) ∈ 0, min 5θ-3 2 , θ -1 2 such that g(θ) := max 0<c<min{ 5θ-3 2 , θ-1 2 } g(θ; c) = g(θ; c(θ)) > 0.
In particular, we have g(1) > g(1; 0.1778) > 0.1063. (iii) For x → ∞, we have

{n x : P (n) < P (n + 1)} > 0.1063x. (1.7)
Theorem 1.(iii) improves Fouvry's constant "0.05866" mentioned above. We shall follow Fouvry's argument [START_REF] De La Bretèche | Products of ratios of consecutive integers[END_REF]. The starting point is the following inequality

x<n x+y P (n-1)<P (n) 1 x<n x+y P (n)>n 1-c 1 - x<n x+y P (n-1)>P (n)>n 1-c 1 =: S A -S B (1.8)
with 0 < c 1 2 . So we only need to give a lower bound of S A and an upper bound of S B . To estimate S A , we shall use the asymptotic formula about the distribution of friable numbers in short intervals.

For S B , if n is counted by S B , then n is of the form n = ap+1 = bp with p > p > n 1-c , namely a < b n c . So we have

S B |{x < n x + y : n = ap + 1 = bp , a < b (x + y) c }| = b (x+y) c |{x < n x + y : n = ap + 1 = bp , a < b}| = b (x+y) c |{n ∈ A (b) : n is prime}|, where A (b) := ap + 1 b : x < ap x + y, a < b, ap + 1 ≡ 0(mod b) . (1.9)
It is because of the substitution of "a < x c " with "a < b" in the above sequence A (b) that we can improve Fouvry's constant "0.05866" to "0.1063". Then we will use Rosser-Iwaniec's sieve [START_REF] Iwaniec | A new form of the error term in the linear sieve[END_REF][START_REF] Iwaniec | Rosser's sieve[END_REF] to sieve A (b) by the following set of primes P = {p : p is prime}, (1.10) so that we can give an upper bound of S B . In addition, we also need some generalized Bombieri-Vinogradov theorems in short intervals [START_REF] Wu | Théorèmes généralisés de Bombieri-Vinogradov dans les petits intervalles[END_REF].

Theorem 2. For large N , we have

log A(N ) {K + o(1)}N log N, (1.11)
where K ≈ 0.1108 is a constant.

Theorem 2 improves the constant K ≈ 0.107005 of Theorem (B).

Lemmas

Let A be a finite sequence of integers, P a set of primes, z 2 a real number and d a squarefree integer with all its prime factors belonging to P, and denote

A d := {a ∈ A : d | a}, P (z) := p<z, p∈P p.
We shall evaluate S(A; P, z) := |{a ∈ A : (a, P (z)) = 1}|.

Assume that |A d | may be written in the form

|A d | = ω(d) d X + r(A, d) for d | P (z),
where X is an approximation to |A| independent of d, ω is a multiplicative function satisfying 0 < ω(p) < p for p ∈ P, ω(d)d -1 X is considered as a main term and r(A, d) is an error term which we expect is small on average over d.

The first lemma is a simple consequence of [5, Theorem 1].

Lemma 2.1. Suppose that there exists a constant K 2 such that

w p<v 1 - ω(p) p -1 < log v log w 1 + K log w
for all v > w 2. Then for any D z 2, we have

S(A; P, z) XV (z) F (s) + O 1 (log y) 1/3 + d<D, d|P (z) |r(A, d)|,
where s := log D/ log z and

V (z) := p<z, p∈P 1 -ω(p)p -1 , F (s) := 2e γ s -1 (0 < s 3).
For (a, q) = 1 and 1, we define π(z; q, a, ) = p z p≡a(mod q)

1.

The second lemma is [START_REF] Wu | Théorèmes généralisés de Bombieri-Vinogradov dans les petits intervalles[END_REF]Theorem]. Lemma 2.2. Let g( ) be an arithmetic function satisfying

x |g( )| 2 -1 L λ
for some positive constant λ > 0. Define H(z, h; q, a, ) := π(z + h; q, a, ) -π(z; q, a, ) -

1 ϕ(q) (z+h)/ z/ dt log t • (2.1)
Then for any A > 0 and ε > 0, there exists a constant B = B(A, λ) > 0 such that the estimate

q Q max (a, q)=1 max h y max x/2<z x L ( , q)=1
g( )H(z, h; q, a, )

A,λ,ε yL -A holds uniformly for 3 5 + ε θ 1, Q = x θ-1/2 L -B and L = x (5θ-3)/2-ε . In particuliar, we can easily see that Lemma 2.2 covers the result of Perelli, Pintz and Salerno [START_REF] Perelli | Bombieri's theorem in short intervals[END_REF], which states that if π(z; q, a) := π(z; q, a, 1), then for any A > 0 we have

q Q max (a, q)=1 max h y max x/2<z x π(z + h; q, a) -π(z; q, a) - 1 ϕ(q) z+h z dt log t yL -A , (2.2)
uniformly for 3 5 < θ 1 and Q = x θ-1/2 L -B , where B = B(A) is a positive constant. The third lemma is [4, Theorem 3]. Lemma 2.3. As Ψ(x, y) is defined by (1.1), then the following asymptotic formula

Ψ(x + z, y) -Ψ(x, y) ∼ z x Ψ(x, y) ∼ z (u) (2.3)
holds uniformly for 1 x/z y 5/12 and exp (log L ) 5/3+ε y x.

Proof of Theorem 1 and 2

For Theorem 1, recall that S A , S B , A (b) and P are defined in (1.8), (1.9) and (1.10) respectively. First, we shall give an upper bound of S B , and then estimate S A .

For S B , we first sieve A (b) by P, and then sum over b. Let θ and c be two positive real numbers satisfying (1.4) respectively, and z = x θ-1/2 /(bL B 0 ), where B 0 is an appropriate positive constant. So for b (x + y) For the first sum on the right hand side of (3.1), we have

a<b (a, bd)=1 1 ϕ(bd) (x+y)/a x/a dt log t = a<b (a, bd)=1 y aϕ(bd) 1 log x a + O 1 log x a - 1 log x+y a = 1 + O 1 L y ϕ(bd) a<b (a, bd)=1 1 a log(x/a)
•

By the Möbius inversion, we have

a<b (a, bd)=1 1 ϕ(bd) (x+y)/a x/a dt log t = 1 + O 1 L y ϕ(bd) a<b 1 a log(x/a) q|(a, bd) µ(q) = 1 + O 1 L y ϕ(bd) q|bd µ(q) q aq<b 1 a log(x/aq) = 1 + O 1 L y ϕ(bd) S 1 + S 2 , (3.2)
where

S 1 := q|bd, q<L 9
µ(q) q a<b/q 1 a log(x/aq) , S 2 := q|bd, q L 9 µ(q) q a<b/q 1 a log(x/aq) •

Denoting by τ (n) the number of divisors of n, we have

S 2 q|bd, q L 9 q -1 τ (bd)L -9 . (3.3)
And for S 1 , by the partial summation we have

S 1 = q|bd, q<L 9 µ(q) q b/q 1 dt t log(x/tq) + O 1 L = q|bd, q<L 9 µ(q) q log log x -log q log x -log b + O 1 L = q|bd, q<L 9 µ(q) q log log x log(x/b) + O log L L ,
owing to the condition q < L 9 , we can separate the above log q from the main term. Thus we have

S 1 = q|bd µ(q) q - q|bd q L 9 µ(q) q log log x log(x/b) + O log L L = ϕ(bd) bd log log x log(x/b) + O log L L + O τ (bd) L 9 . (3.4)
So we infer from (3.1), (3.2), (3.3) and (3.4) that

|A d (b)| = ω(d) d X + r(A (b), d)
with ω(d) = 1 and

X = y b log log x log(x/b) 1 + O log L L , r(A (b), d) = a<b (a, bd)=1 H(x, y; bd, -1, a) + O yτ (bd) ϕ(bd)L 9 .
Thus we can apply Lemma 2.1 with D = z = x θ-1/2 /(bL B 0 ) to write

S(A (b); P, z) {1 + o(1)} 2X log(x θ-1/2 /b) + d<z, d|P (z) |r(A (b), d)|,
where we have used Mertens' formula to evaluate

V (z) = p<x θ-1/2 b -1 L -B 0 1 - 1 p = e -γ log(x θ-1/2 /b) 1 + O log L L .
From this and the trivial inequality First we evaluate the error term S 4 . By the Cauchy-Schwarz inequality, it follows that

S 4 m<x θ-1/2 L -B 0 τ (m) a<b (a, m)=1 H(x, y; m, -1, a) (S 41 S 42 ) 1/2 ,
where

S 41 := m<x θ-1/2 L -B 0 a<b (a, m)=1 H(x, y; m, -1, a) , S 42 := m<x θ-1/2 L -B 0 τ (m) 2 a<b (a, m)=1 H(x, y; m, -1, a) .
For S 42 , we use a trivial estimate and for S 41 , we shall apply Lemma 2.2 with

g( ) = 1 if 0 < b 0 if b <
x (5θ-3)/2-ε since b (x + y) c x (5θ-3)/2-ε thanks to hypothesis (1.4). So we obtain

S 4 y L A 1/2 m<x θ-1/2 L -B 0 τ (m) 2 a<b y am + O(1) 1/2 y L A 1/2 yL 5 + bx θ-1/2 L -B 0 +3 1/2 y L A/2-3 (3.6) since y 1/2 x (c+θ-1/2)/2 yx -(1/2-c)/2 y with c < θ -1 2 1
2 . Next we evaluate S 3 . By partial summation we get

S 3 = 2y{1 + o(1)} (x+y) c 1 log log x log(x/t) dt t log(x θ-1/2 /t) = y 2 c 0 log(1 -v) -1 θ -1 2 -v dv + o θ, c (
S B y 2 c 0 log(1 -v) -1 θ -1 2 -v dv + o c, θ (1) . (3.8)
Finally we evaluate S A . Noticing that 3 5 < θ 1, 0 < c < θ-1 2 1 2 and (u) = 1-log u for 1 u 2, Lemme 2.3 gives us immediately We have

S A = y log 1 1 -c + o c, θ (1)
∂g ∂c (θ; c) = 1 1 -c -2 log(1 -c) -1 θ -1 2 -c , ∂ 2 g ∂c 2 (θ; c) = - 1 1 -c 2 θ -1 2 -c - 1 1 -c -2 log(1 -c) -1 (θ -1 2 -c) 2 •
It's obvious that ∂ 2 g ∂c 2 (θ; c) < 0 for 3 5 < θ 1 and 0 c < θ - This completes the proof of Theorem 1.

For Theorem 2, just as discussed in [START_REF] De La Bretèche | Products of ratios of consecutive integers[END_REF], the lower bound (1.11) is an easy consequence of (3.8) with y = x and 0 < c < 1/2. So we have

2 3 +

 3 o(1) N log N, and further a brief argument of M.Langevin is presented that log A(N ) {log 4 + o(1)}N.

3 5 < θ 1

 31 and 0 < c < min 5θ-3 2 , θ -1 2 .

  c and d | P (z), we have |A d (b)| = ap + 1 b : x < ap x + y, a < b, ap + 1 ≡ 0 (mod bd) = a<b x<ap x+y ap+1≡0(mod bd) 1.With the notation (2.1) we can write as follows|A d (b)| = bd)=1H(x, y; bd, -1, a).(3.1)

9 b 9 m<x 1 / 2 L

 9912 |{n ∈ A (b) : n is prime}| S(A (b); P, z) + z, we deduce S B b (x+y) c(S(A (b); P, z) + z) {1 + o(1)}S 3 + S 4 + O yL -1 , (3.5) where S 3 := b (x+y) c 2y b log(x θ-1/2 /b) log log x log(x/b) , S 4 := b (x+y) c d<z a<b (a, bd)=1 H(x, y; bd, -1, a) , and we have used the standard estimation m x τ (m) 2 /ϕ(m) L 4 to bound yL -(x+y) c d<x θ-1/2 /(bL B 0 ) τ (bd) ϕ(bd) yL -

1 ) . ( 3 . 7 )

 137 So from (3.5), (3.6) and (3.7) we obtain

Figure 1 :

 1 Figure 1: g(θ)

1 2 .

 2 Thus c → ∂g ∂c (θ; c) is decreasing. Since ∂g ∂c (θ; 0) = 1 and lim c→(θ-1 2 )-∂g ∂c (θ; c) = -∞, there is a unique c(θ) ∈ 0, min{ 5θ-3 2 , θ -1 2 } such that ∂g ∂c (θ; c(θ)) c) = g(θ; c(θ)) > g(θ; 0) = 0 for 3 5 < θ 1.By Mathematica 9.0, we can find c(1) ≈ 0.1778 and g(1) = g(1, c(1)) > 0.1063. The assertion (iii) is an immediate consequence of the first two ones thanks to a simple dyadic summation.

  log A(N ) 2N (log N ){g(c) + o(1)}, where g(c) := c -(1 -c)f (c) -c 0 f (u)du, with f (u) := 4 ) ≈ 0.1108.This completes the proof of Theorem 2.

Acknowledgement. This paper is directed by the author's advisors of thesis C. Dartyge and J. Wu. The author expresses his sincere gratitude to them for their lot of uesful and crucial advice. Also he thanks Professeur Wenguang Zhai for a crucial suggestion.

The author is supported by the China Scholarship Council.


XIAODONG Bin Chen

Zhiwei Wang
email: wangzhiwei.sdu@gmail.com

Xiaodong Lü

ON THE SMOOTH VALUES OF SHIFTED ALMOST-PRIMES

Keywords: Mathematics Subject Classification. 11N05, 11N36 shifted almost-primes, friable numbers, sieve methods

Denote by P + (n) (resp. P -(n)) the largest (resp. the smallest) prime factor of the integer n 1. In this paper, we prove a lower bound of almost-primes n x with P -(n) > x 1/v , v > 4 such that P + (n -a)

x 1/u for 1 u 1, a ∈ Z, a = 0. As an application, we study two patterns on the largest prime factors of consecutive integers with one of which without small prime factor.

Introduction

For each integer n 1, let P + (n) denote the largest prime factor of n with the convention that P + (1) = 1. The distribution of the largest prime factors of shifted primes P + (p -a) with a ∈ Z, a = 0 have been studied by many mathematicians, such as Erdős [START_REF] Erdős | On the normal number of prime factors of p -1 and some related problems concerning Euler's φ-function[END_REF], Goldfeld [START_REF] Goldfeld | On the number of primes p for which p+a has a large prime factor[END_REF], Pomerance [START_REF] Pomerance | Popular values of Euler's function[END_REF], Fouvry [START_REF] Fouvry | Théorème de Brun-Titchmarsh; application au théorème de Fermat[END_REF], Baker and Harman [START_REF] Baker | The Brun-Titchmarsh theorem on average[END_REF], Banks and Shparlinski [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF]. Define π(x, y) := (1.1)

In 2008, Granville [START_REF] Granville | Smooth numbers: computational number theory and beyond[END_REF] stated that the asymptotic formula π(x, y) ∼ ρ(u)π(x), y = x 1/u (

follows for all fixed u 1 from a weak form of the Elliott-Halberstam conjecture, a wellbelieved conjecture in analytic number theory. Here ρ(u) is the Dickman-de Bruijn function, and π(x) denotes the number of primes not exceeding x. Recently the second named author [START_REF] Wang | Autour des plus grands facteurs premiers d'entiers consécutifs voisins d'un entier criblé[END_REF] provided the details for proof of (1.2) under the Elliott-Halberstam conjecture.

In this paper, we consider the analogue problem via replacing prime p by almost-prime (with a limited number of prime factors). For a ∈ Z, y x and z x, we define

Φ(x, y, z) := n x, P -(n)>z P + (n-a) y 1, (1.3)
where P -(n) denotes the smallest prime factor of integer n with the convention P -(1) = ∞.

For the case a = 0, we may refer to the work of Friedlander [START_REF] Friedlander | Integers free from large and small primes[END_REF] and Saias [START_REF] Saias | Entiers sans grand ni petit facteur premier I[END_REF][START_REF] Saias | Entiers sans grand ni petit facteur premier II[END_REF][START_REF] Saias | Entiers sans grand ni petit facteur premier III[END_REF]. Here we only consider the case a = 0. Considering the following formula for almost-primes (see [24, Chapitre III.6]):

Φ(x, z) := n x P -(n)>z 1 = xω(v) -z log z + O x (log z) 2 , z = x 1/v
for x z 2, where ω(v) is the Buchstab function, we may guess that

Φ(x, y, z) ∼ ρ(u)ω(v) x log z , y = x 1/u , z = x 1/v (1.4)
for some u, v 1.

It's not difficult to prove (1.4) with 1 v, 1 u 1 under the Elliott-Halberstam conjecture for almost-primes (replacing primes by almost-primes) by following the argument of Lemma 4.1 in [START_REF] Wang | Autour des plus grands facteurs premiers d'entiers consécutifs voisins d'un entier criblé[END_REF]. We leave the details to the interested reader.

In this paper, we first prove an unconditional result on the estimate of Φ(x, y, z) for some u, v 1.

Theorem 1. For x → ∞ and y = x 1/u , z = x 1/v , there exists a strictly positive constant c 1 (u, v) such that Φ(x, y, z) c 1 (u, v)

x log x

(1.5)

for v > 4, 1 u 1.
Remark. With the same method to (1.5), we can obtain an upper bound

Φ(x, y, z) c 2 (u, v) x log x (1.6) for 1 v 1, 1 u 1, where c 2 (u, v
) is a strictly positive constant. In fact, (1.6) is the case "q = 1" of Theorem 1 in [START_REF] Liu | Primes in arithmetic progressions with friable indices[END_REF]. An application of the upper bound (1.6) is to study the density of shifted primes with large prime factors. For 0 < θ < 1, we define T θ (x) := p x : P + (p -1) p θ , and we want to estimate T θ (x) with a good lower bound (see [START_REF] Luca | On shifted primes with large prime factors and their products[END_REF], [START_REF] Chen | On the largest prime factor of shifted primes[END_REF] and [START_REF] Feng | On the density of shifted primes with large prime factors[END_REF]). As in the very recent work of Liu, Wu and Xi [START_REF] Liu | Primes in arithmetic progressions with friable indices[END_REF], with the help of (1.6), for x → ∞ we have the following lower bound

T θ (x)        1 -4ρ(1/θ) + o(1)
x log x for 0 < θ θ 0 ,

1 -θ + o(1) x log x for θ 0 < θ 1/2, (1.7)
where θ 0 ≈ 0.3734.

As an application of Theorem 1, we treat a problem on the largest prime factors of consecutive integers with one of which almost-prime. In [START_REF] Wang | Autour des plus grands facteurs premiers d'entiers consécutifs voisins d'un entier criblé[END_REF], the second named author first exploited this problem and proved that there exists a strictly positive constant C(β) such that

n x, P -(n)>x β P + (n)<P + (n+2) 1 C(β) + o(1) x log x (1.8) for 0 < β < 1 3 . Taking β = 1 3 -δ with 0 < δ 1 12 in (1.8)
, we obtain the lower bound

P 3 x, P -(P 3 )>x 1/3-δ P + (P 3 )<P + (P 3 +2) 1 C( 1 3 -δ) + o(1) x log x (1.9)
for 0 < δ 1 12 . Here P 3 denotes an integer having at most three prime factors counted with multiplicity, i.e. P 3 is an almost-prime. The most interesting case in this problem is undoubtedly on primes, i.e. replacing P 3 in (1.9) by a prime number p, or equivalently, extend the value of β in (1.8) to 0 < β 1 2 , considering the well-known twin prime conjecture is equivalent to

|{p x : P + (p) < P + (p + 2)}| → ∞ for x → ∞.
In addition, it should be noted that we can obtain a result similar to (1.8) directly for the small values of β by a result of Fouvry [18, Théorème 2], a theorem of Bombieri-Vinogradov type on sifted integers (without small prime factor) with an exponent of distribution > 1 2 , or applying a weighted sieve combined with a theorem of Bombieri-Vinogradov type (see Fouvry [START_REF] Fouvry | Autour du théorème de Bombieri-Vinogradov[END_REF]Théorème 2] and [START_REF] Fouvry | Répartition des suites dans les progressions arithmétiques[END_REF]Corollaire 3]).

In this paper, we treat the dual problem of (1.8), i.e. we replace the condition P + (n) < P + (n + 2) by P + (n) > P + (n + 2) with n free of small prime factor. In fact, this problem was posed by Fouvry in the thesis report that he wrote for the second named author. With the help of (1.5), and the lower bound of Φ(x, y, z) in Theorem 1, we prove that there exists a positive density of n such that P + (n) > P + (n + 2), P -(n) > x α with 0 < α < 1 4 :

Corollary 1. For x → ∞ and 0 < α < 1 4 , there exists a strictly positive constant C 1 (α) such that

n x, P -(n)>x α P + (n)>P + (n+2) 1 C 1 (α) + o(1) x log x . (1.10)
It would be interesting to extend the domain of α to 0 < α < 1 2 .

Lemmas

The first lemma is the Rosser-Iwaniec sieve [START_REF] Iwaniec | A new form of the error term in the linear sieve[END_REF]. Here we only employ the upper-bound sieve.

λ + d w(d) d p z p∈P 1 - w(p) p F (s) + O e L 1/2 -s (log D) 1/3 , d|P (z) λ - d w(d) d p z p∈P 1 - w(p) p f (s) -O e L 1/2 -s (log D) 1/3
uniformly for all multiplicative functions w satisfying

(i) 0 < w(p) < p (p ∈ P), (ii) u<p v p∈P 1 - w(p) p -1 log v log u 1 + L log u (2 u v z).
where s = log D/ log z and F (s), f (s) are defined by the continuous solutions to the system

           sF (s) = 2e γ 1 s 2, sf (s) = 0 0 < s 2, (sF (s)) = f (s -1) s > 2, (sf (s)) = F (s -1) s > 2.
Here γ is the Euler constant.

Define S(x, y) := n x : P + (n) y , Ψ(x, y) := |S(x, y)| (2.1) and Ψ(x, y; a, q) := n∈S(x, y) n≡a(mod q)

1, Ψ q (x, y) :

= n∈S(x, y) (n, q)=1
1.

(2.

2)

The following two lemmas are on the distribution of friable numbers, obtained by Hildebrand [15, Theorem 1] and Fouvry-Tenenbaum [10, Théorème 1] respectively.

Lemma 2.2. For ε > 0, we have

Ψ(x, y) = xρ(u) 1 + O ε log(u + 1) log y
uniformly for x x 0 (ε), exp{(log 2 x) 5/3+ε } y x, where u = log x/ log y and ρ(u) is the Dickman-de Bruijn function.

Lemma 2.3. For ε > 0, we have

Ψ q (x, y) = ϕ(q) q Ψ(x, y) 1 + O log 2 (qy) log 2 x log y
uniformly for x x 0 (ε), exp{(log 2 x) 5/3+ε } y x and log 2 (q + 2) log y log(u + 1)

1-ε

, where u = log x/ log y and ϕ(n) is the Euler function.

The fourth lemma is the Bombieri-Vinogradov theorem for friable numbers, concerning the distribution of friable numbers in arithmetic progressions, averaged over a range of moduli. For Ψ(x, y; a, q) and Ψ q (x, y) defined by (2.2), we have Lemma 2.4. For any A > 0, there exists a constant B = B(A) > 0 such that

q x 1/2 /(log x) B max x x max (a, q)=1 Ψ(x , y; a, q) - Ψ q (x , y) ϕ(q) A x (log x) A (2.3)
uniformly for x y 2.

In [START_REF] Wolke | Über die mittlere verteilung der werte zahlentheoretischer funktionen auf restklassen[END_REF], Wolke proved a theorem of Bombieri-Vinogradov for sifted numbers, and announced Lemma 2.4. In 1991, Fouvry and Tenenbaum [START_REF] Fouvry | Entiers sans grand facteur premier en progressions arithmétiques[END_REF] proved Lemma 2.4 with a different method. In addition, for Lemma 2.4, we can see the work of Fouvry and Tenenbaum (also the work of Drappeau [START_REF] Drappeau | Théorèmes de type Fouvry-Iwaniec pour les entiers friables[END_REF]) with the level of the distribution of friable numbers > 1/2 for some small y, or the work of Harper [START_REF] Harper | Bombieri-Vinogradov and Barban-Davenport-Halberstam type theorems for smooth numbers[END_REF].

Proof of Theorem 1

For Φ(x, y, z) defined by (1.3) with y = x 1/u , z = x 1/v and any a ∈ Z * fixed, we apply Lemma 2.1 by taking P = {p : p is prime, p a}. 1 .

Taking D = x 1/2 /(log x) B for convenable B > 0, we see that the error term R(x, y, z) is admissible with the help of Lemma 2.4

R(x, y, z) = d D, d|P (z) λ - d n x, P + (n) y n≡-a(mod d) 1 - 1 ϕ(d) n x, P + (n) y (n, d)=1 1 |(n, a) µ( ) = d D, d|P (z) λ - d |a µ( ) m x/ , P + (m) y m≡-a (mod d) 1 - 1 ϕ(d) m x/ , P + (m) y (m, d)=1 1 d D max x x max (a , d)=1 Ψ(x , y; a , d) - Ψ d (x , y) ϕ(d) x (log x) A (3.3)
for any A > 0 and any fixed integer a = 0. Now it remains to estimate M (x, y, z). We first change the order of summation and write

M (x, y, z) = n x, (n, a)=1 P + (n) y d D d|P (z) λ - d ϕ(d)
where P (z) = p<z, p∈P p with P := {p : p an}. Note that by (3.1) we may deduce that n and a have opposite parity which implies 2|an. We apply Lemma 2.1 with w(p) = p/ϕ(p) and some large constant L getting

M (x, y, z) f v 2 -o(1) n x, (n, a)=1 P + (n) y 2<p z p an 1 - 1 p -1 = f v 2 -o(1) 2<p z p a p -2 p -1 n x, (n, a)=1 P + (n) y H(n)
where H(n) is a multiplicative function defined by

H(n) = 2<p z, p|n p -1 p -2 .
By the following formula due to Liu-Wu-Xi (see [17, (3.5) for y = x 1/u , z = x 1/v with v > 4, 1 u 1. This completes the proof of Theorem 1.

Proof of Corollary 1

For 0 < α < 1 4 , we have By taking z = x α and a = -2 in (1.5) of Theorem 1, we obtain Corollary 1.

Lemma 2 . 1 .

 21 Let D 2 and L > 1. Let P denote a set of primes, let z 2 and write P (z) := p z,p∈P p. There exists two sequences λ ± d ∞ d=1 of real numbers, vanishing for d > D or µ(d) = 0, satisfying λ ± 1 = 1, λ ± d 1, λ - * 1 µ * 1 λ + * 1, and such that d|P (z)

  So we have Φ(x, y, z) = n x+a, (n, a)=1 P + (n-a) y (n, P (z))=1 1 + O(1) = n x+a, (n, a)=1 P + (n-a) y µ * 1 (n, P (z)) + O(1) (n, a)=1 P + (n) y n≡-a(mod d) 1 + O(1).

( 3 . 1 )

 31 Then we write this in the following formΦ(x, y, z) M (x, y, z) + R(x, y, z) + O(1) , y, z) := d D, d|P (z) λ - d n x, (n, a)=1 P + (n) y n≡-a(mod d) 1 -1 ϕ(d) n x, (n, a)=1 P + (n) y (n, d)=1

  n x, P -(n)>x α P + (n)>P + (n+2) 1 n x, P -(n)>x α P + (n+2)<x α 1.

Acknowledgements The authors first are very grateful to Professor Valentin Blomer for pointing out a mistake in the original version of the paper [18]. The authors would like to express the most sincere gratitude to Professor Étienne Fouvry for posing the question in Corollary 1, which is the original motivation of this paper. The authors would also like to thank Professors Cecile Dartyge and Jie Wu for their valuable advice and constant encouragement. The second author is supported by the China Postdoctoral Science Foundation (No. 2017M621829), the Jiangsu Province Postdoctoral Science Foundation (No. 1701142C) and the Yangzhou University Overseas Study Program. The first and third authors are supported by China Scholarship Council, and the third author is partly supported by the NSFC(61402335), SRPF-SXPED(17JK0266), NSF-WNU(17ZRRC01).