Thomas Stoll
email: stoll@iml.univ-mrs.fr

The sum of digits of polynomial values in arithmetic progressions

Keywords: 2010 Mathematics Subject Classification: Primary 11A63; Secondary 11N37, 11N69 sum of digits, polynomials, Gelfond's problem

, which is CN 2/h! .

Introduction

Let q, m ≥ 2 be integers and denote by s q (n) the sum of digits of n in the q-ary digital expansion of integers. In 1967/68, Gelfond [START_REF] Gelfond | Sur les nombres qui ont des propriétés additives et multiplicatives données[END_REF] proved that for nonnegative integers a 1 , a 0 with a 1 = 0, the sequence (s q (a 1 n + a 0 )) n∈N is well distributed in arithmetic progressions mod m, provided (m, q -1) = 1. At the end of his paper, he posed the problem of finding the distribution of s q in arithmetic progressions where the argument is restricted to values of polynomials of degree ≥ 2. Recently, Mauduit and Rivat [START_REF] Mauduit | La somme des chiffres des carrés[END_REF] answered Gelfond's question in the case of squares.

Theorem 1.1 [START_REF] Mauduit | La somme des chiffres des carrés[END_REF]). For any q, m ≥ 2 there exists σ q,m > 0 such that for any g ∈ Z, as N → ∞, #{0 ≤ n < N : s q (n 2 ) ≡ g mod m} = N m Q(g, d) + O q,m (N 1-σq,m ),

where d = (m, q -1) and

Q(g, d) = #{0 ≤ n < d : n 2 ≡ g mod d}.
The proof can be adapted to values of general quadratic polynomial instead of squares. We refer the reader to [START_REF] Mauduit | Sur un problème de Gelfond: la somme des chiffres des nombres premiers[END_REF] and [START_REF] Mauduit | La somme des chiffres des carrés[END_REF] for detailed references and further historical remarks. The case of polynomials of higher degree remains elusive so far. The Fourier-analytic approach, as put forward in [START_REF] Mauduit | Sur un problème de Gelfond: la somme des chiffres des nombres premiers[END_REF] and [START_REF] Mauduit | La somme des chiffres des carrés[END_REF], seems not to yield results of the above strength. In a recent paper, Drmota, Mauduit and Rivat [START_REF] Drmota | The sum of digits function of polynomial sequences[END_REF] applied the Fourier-analytic method to show that well distribution in arithmetic progressions is obtained whenever q is sufficiently large.

In the sequel, and unless otherwise stated, we write

p(x) = a h x h + • • • + a 0 for an arbitrary, but fixed polynomial p(x) ∈ Z[x] of degree h ≥ 3 with p(N) ⊂ N. Theorem 1.2 (Drmota, Mauduit & Rivat (2011)). Let q ≥ exp(67h 3 (log h) 2 )
be a sufficiently large prime number and suppose (a h , q) = 1. Then there exists σ q,m > 0 such that for any g ∈ Z, as N → ∞,

#{0 ≤ n < N : s q (p(n)) ≡ g mod m} = N m Q (g, d) + O q,m,p (N 1-σq,m ),
where d = (m, q -1) and

Q (g, d) = #{0 ≤ n < d : p(n) ≡ g mod d}.
It seems impossible to even find a single "nice" polynomial of degree 3, say, that allows to conclude for well distribution in arithmetic progressions for small bases, let alone that the binary case q = 2 is an emblematic case. Another line of attack to Gelfond's problem is to find lower bounds that are valid for all q ≥ 2. Dartyge and Tenenbaum [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF] provided such a general lower bound by a method of descent on the degree of the polynomial and the estimations obtained in [START_REF] Dartyge | Sommes de chiffres de multiples d'entiers[END_REF].

Theorem 1.3 [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF]). Let q, m ≥ 2 with (m, q -1) = 1. Then there exist C = C(q, m, p) > 0 and N 0 = N 0 (q, m, p) ≥ 1, such that for all g ∈ Z and all N ≥ N 0 ,

#{0 ≤ n < N : s q (p(n)) ≡ g mod m} ≥ CN 2/h! .
The aim of the present work is to improve this lower bound for all h ≥ 3. More importantly, we get a substantial improvement of the bound as a function of h. The main result is as follows. 1Theorem 1.4. Let q, m ≥ 2 with (m, q -1) = 1. Then there exist C = C(q, m, p) > 0 and N 0 = N 0 (q, m, p) ≥ 1, such that for all g ∈ Z and all

N ≥ N 0 , #{0 ≤ n < N : s q (p(n)) ≡ g mod m} ≥ CN 4/(3h+1) .
Moreover, for monomials p(x) = x h , h ≥ 3, we can take

N 0 = q 3(2h+m) 2hq 2 (6q) h 3h+1 , C = 16hq 5 (6q) h • q (24h+12m)/(3h+1) -1 .
The proof is inspired from the constructions used in [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF] and [START_REF] Hare | The sum of digits of n and n 2[END_REF] that were helpful in the proof of a conjecture of Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF] concerning the pointwise distribution of s q (p(n)) versus s q (n). As a drawback of the method of proof, however, it seems impossible to completely eliminate the dependency on h in the lower bound.

Proof of Theorem 1.4

Consider the polynomial

t(x) = m 3 x 3 + m 2 x 2 -m 1 x + m 0 , (2.1)
where the parameters m 0 , m 1 , m 2 , m 3 are positive real numbers that will be chosen later on in a suitable way. For all integers l ≥ 1 we write

T l (x) = t(x) l = 3l i=0 c i x i (2.2)
to denote its l-th power. (For the sake of simplicity we omit to mark the dependency on l of the coefficients c i .) The following technical result is the key in the proof of Theorem 1.4. It shows that, within a certain degree of uniformity in the parameters m i , all coefficients but one of T l (x) are positive.

Lemma 2.1. For all integers q ≥ 2, l ≥ 1 and m 0 , m 1 , m 2 , m 3 ∈ R + with

1 ≤ m 0 , m 2 , m 3 < q, 0 < m 1 < l -1 (6q) -l
we have that c i > 0 for i = 0, 2, 3, . . . , 3l and c i < 0 for i = 1. Moreover, for all i,

|c i | ≤ (4q) l . (2.3)
Proof. The coefficients of T l (x) in (2.2) are clearly bounded above in absolute value by the corresponding coefficients of the polynomial (qx 3 + qx 2 + qx + q) l . Since the sum of all coefficients of this polynomial is (4q) l and all coefficients are positive, each individual coefficient is bounded by (4q) l . This proves (2.3). We now show the first part. To begin with, observe that c 0 = m l 0 > 0 and c 1 = -lm 1 m l-1 0 which is negative for all m 1 > 0. Suppose now that 2 ≤ i ≤ 3l and consider the coefficient of x i in

T l (x) = (m 3 x 3 + m 2 x 2 + m 0 ) l + r(x), (2.4)
where

r(x) = l j=1 l j (-m 1 x) j m 3 x 3 + m 2 x 2 + m 0 l-j = 3l-2 j=1 d j x j .
First, consider the first summand in (2.4). Since m 0 , m 2 , m 3 ≥ 1 the coefficient of x i in the expansion of (m

3 x 3 + m 2 x 2 + m 0 ) l is ≥ 1.
Note also that all the powers x 2 , x 3 , . . . , x 3l appear in the expansion of this term due to the fact that every i ≥ 2 allows at least one representation as i = 3i 1 + 2i 2 with non-negative integers i 1 , i 2 . We now want to show that for sufficiently small m 1 > 0 the coefficient of x i in the first summand in (2.4) is dominant. To this end, we assume m 1 < 1 so that m 1 > m j 1 for 2 ≤ j ≤ l. Using l j < 2 l and a similar reasoning as above we get that

|d j | < l2 l m 1 (3q) l = l (6q) l m 1 , 1 ≤ j ≤ 3l -2.
This means that if m 1 < l -1 (6q) -l then the powers x 2 , . . . , x 3l in the polynomial T l (x) indeed have positive coefficients. This finishes the proof.

To proceed we recall the following splitting formulas for s q which are simple consequences of the q-additivity of the function s q (see [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF] for the proofs). Proposition 2.2. For 1 ≤ b < q k and a, k ≥ 1, we have s q (aq k + b) = s q (a) + s q (b), s q (aq k -b) = s q (a -1) + k(q -1) -s q (b -1).

We now turn to the proof of Theorem 1.4. To clarify the construction we consider first the simpler case of monomials,

p(x) = x h , h ≥ 1.
(We here include the cases h = 1 and h = 2 because we will need them to deal with general polynomials with linear and quadratic terms.) Let u ≥ 1 and multiply t(x) in (2.1) by q u-1 . Lemma 2.1 then shows that for all integers m 0 , m 1 , m 2 , m 3 with

q u-1 ≤ m 0 , m 2 , m 3 < q u , 1 ≤ m 1 < q u /(hq(6q) h ), (2.5)
the polynomial T h (x) = (t(x)) h = p(t(x)) has all positive (integral ) coefficients with the only exception of the coefficient of x 1 which is negative. Let u be an integer such that q u ≥ 2hq(6q) h (2.6)

and let k ∈ Z be such that

k > hu + 2h. (2.7)
For all u with (2.6) the interval for m 1 in (2.5) is non-empty. Furthermore, relation (2.7) implies by (2.3) that

q k > q hu • q 2h ≥ (4q u ) h > |c i |, for all i = 0, 1, . . . , 3h,
where c i here denotes the coefficient of x i in T h (x). Roughly speaking, the use of a large power of q (i.e. q k with k that satisfies (2.7)) is motivated by the simple wish to split the digital structure of the h-power according to Proposition 2.2. By doing so, we avoid to have to deal with carries when adding terms in the expansion in base q since the appearing terms will not interfere. We also remark that this is the point where we get the dependency of h in the lower bound of Theorem 1.4. Now, by c 2 , |c 1 | ≥ 1 and the successive use of Proposition 2.2 we get

s q (t(q k ) h ) = s q 3h i=3 c i q ik + c 2 q 2k -|c 1 |q k + c 0 = s q 3h i=3 c i q (i-1)k + c 2 q k -|c 1 | + s q (c 0 ) = s q 3h i=3 c i q (i-3)k + s q (c 2 -1) + k(q -1) -s q (|c 1 | -1) + s q (c 0 ) = 3h i=3 s q (c i ) + s q (c 2 -1) + k(q -1) -s q (|c 1 | -1) + s q (c 0 ) = k(q -1) + M, (2.8)
where we write

M = 3h i=3 s q (c i ) + s q (c 2 -1) -s q (|c 1 | -1) + s q (c 0 ).
Note that M is an integer that depends (in some rather obscure way) on the quantities m 0 , m 1 , m 2 , m 3 . Once we fix a quadruple (m 0 , m 1 , m 2 , m 3 ) in the ranges (2.5), the quantity M does not depend on k and is constant whenever k satisfies (2.7). We now exploit the appearance of the single summand k(q -1) in (2.8). Since by assumption (m, q -1) = 1, we find that s q (t(q k ) h ), for k = hu + 2h + 1, hu + 2h + 2, . . . , hu + 2h + m, (2.9) runs through a complete set of residues mod m. Hence, in any case, we hit a fixed arithmetic progression mod m (which might be altered by M ) for some k with hu + 2h + 1 ≤ k ≤ hu + 2h + m. Summing up, for u with (2.6) and by (2.5) we find at least (q u -q u-1 ) 3 (q u /(hq(6q) h ) -1) ≥ (1 -1/q) 3 2hq (6q) h q 4u (2.10) integers n that in turn by (2.1), (2.5), (2.7) and (2.9) are all smaller than q u • q 3(hu+2h+m) = q 3(2h+m) • q u(3h+1)

and satisfy s q (n h ) ≡ g mod m for fixed g and m. By our construction and by choosing k > hu + 2h > u all these integers are distinct. We denote N 0 = N 0 (q, m, p) = q 3(2h+m) • q u 0 (3h+1) , where u 0 = log q 2hq(6q) h ≤ log q 2hq 2 (6q) h .

Then for all N ≥ N 0 we find u ≥ u 0 with q 3(2h+m) • q u(3h+1) ≤ N < q 3(2h+m) • q (u+1)(3h+1) .

(2.11) By (2.10) and (2.11), and using (1 -1/q) 3 ≥ 1/8 for q ≥ 2, we find at least

(1 -1/q) 3 2hq (6q) h q 4u ≥ 16hq 5 (6q) h • q (24h+12m)/(3h+1) -1 N 4/(3h+1)
integers n with 0 ≤ n < N and s q (n h ) ≡ g mod m. We therefore get the statement of Theorem 1.4 for the case of monomials p(x) = x h with h ≥ 3. The estimates are also valid for h = 1 and h = 2.

The general case of a polynomial p(x) = a h x h + • • • + a 0 of degree h ≥ 3 (or, more generally, of degree h ≥ 1) follows easily from what we have already proven. Without loss of generality we may assume that all coefficients a i , 0 ≤ i ≤ h, are positive, since otherwise there exists e = e(p) depending only on p such that p(x + e) has all positive coefficients. Note that a finite translation can be dealt with choosing C and N 0 appropriately in the statement. Since Lemma 2.1 holds for all l ≥ 1 and all negative coefficients are found at the same power x 1 , we have that the polynomial p(t(x)) has again all positive coefficients but one where the negative coefficient again corresponds to the power x 1 . It is then sufficient to suppose that k > hu + 2h + log q max 0≤i≤h a i in order to split the digital structure of p(t(q k )). In fact, this implies that

q k > max 0≤i≤h a i • (4q u ) h ,
and exactly the same reasoning as before yields q,p q 4u distinct positive integers that are q,m,p q u(3h+1) and satisfy s q (p(n)) ≡ g mod m. This completes the proof of Theorem 1.4.

Gelfond's work and Theorem 1.1 give precise answers for linear and quadratic polynomials, so we do not include the cases h = 1

, 2 in our statement though our approach works without change.

Acknowledgements

This research was supported by the Agence Nationale de la Recherche, grant ANR-10-BLAN 0103 MUNUM.


Kevin G Hare
email: kghare@math.uwaterloo.ca

Shanta Laishram
email: shanta@iiserbhopal.ac.in

Thomas Stoll
email: stoll@iml.univ-mrs.fr

STOLARSKY'S CONJECTURE AND THE SUM OF DIGITS OF POLYNOMIAL VALUES

come

Introduction

Let q ≥ 2 and denote by s q (n) the sum of digits in the q-ary representation of an integer n. In recent years, much effort has been made to get a better understanding of the distribution properties of s q regarding certain subsequences of the positive integers. We mention the ground-breaking work by C. Mauduit and J. Rivat on the distribution of s q of primes [START_REF] Mauduit | Sur un probléme de Gelfond: la somme des chiffres des nombres premiers[END_REF] and of squares [START_REF] Mauduit | La somme des chiffres des carrés[END_REF]. In the case of general polynomials p(n) of degree h ≥ 2 very little is known. For the current state of knowledge, we refer to the work of C. Dartyge and G. Tenenbaum [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF], who provided some density estimates for the evaluation of s q (p(n)) in arithmetic progressions. The authors [START_REF] Hare | The sum of digits of n and n 2[END_REF] recently examined the special case when s q (p(n)) ≈ s q (n).

A problem of a more elementary (though, non-trivial) nature is to study extremal properties of s q (p(n)). Here we will always assume that [START_REF] Bassily | Distribution of the values of q-additive functions on polynomial sequences[END_REF] p

(x) = a h x h + a h-1 x h-1 + • • • + a 0 ∈ Z[x]
is a polynomial of degree h ≥ 2 with leading coefficient a h > 0.

In the binary case when q = 2, B. Lindström [START_REF] Lindström | On the binary digits of a power[END_REF] showed that

(2) lim sup

n→∞ s 2 (p(n)) log 2 n = h.
In the proof of (2), Lindström uses a sequence of integers n with many 1's in their binary expansions such that p(n) also has many 1's. The special case p(n) = n 2 of (2) has been reproved by M. Drmota and J. Rivat [START_REF] Drmota | The sum-of-digits function of squares[END_REF] with constructions due to J. Cassaigne and G. Baron. On the other hand, it is an intriguing question whether it is possible to generate infinitely many integers n such that p(n) has few 1's compared to n. If this is possible, then this is indeed a rare event. It is well-known [START_REF] Delange | Sur la fonction sommatoire de la fonction "somme des chiffres[END_REF][START_REF] Peter | The summatory function of the sum-of-digits function on polynomial sequences[END_REF] that the average order of magnitude of s q (n) and

s q (n h ) is (3) n<N s q (n) ∼ 1 h n<N s q (n h ) ∼ q -1 2 log q N log N.
In particular, the average value of s q (n h ) is h times larger than the average value of s q (n).

In 1978, K. Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF] proved several results on the extremal values of s q (p(n))/s q (n) for the special case when q = 2 and p(n) = n h . He showed that the maximal order of magnitude is

c(h)(log 2 n) 1-1/h ,
where c(h) only depends on h. This result is best possible, which follows from the Bose-Chowla theorem [START_REF] Bose | Theorems in the additive theory of numbers[END_REF][START_REF] Halberstam | Sequences, Second edition[END_REF]. His proof can be generalized to base q and to general polynomials p(n). Although this generalization is straightforward, we include it here for completeness. Recall that p(n) may have negative coefficients as well. (1) If p(n) has only nonnegative coefficients then there exists c 1 , dependent only on p(x) and q, such that for all n ≥ 2,

s q (p(n)) s q (n) ≤ c 1 (log q n) 1-1/h .
This is best possible in that there is a constant c 1 , dependent only on p(x), such that

s q (p(n)) s q (n) > c 1 (log q n) 1-1/h
infinitely often. (2) If p(n) has at least one negative coefficient then there exists c 2 and n 0 , dependent only on p(x) and q, such that for all n ≥ n 0 ,

s q (p(n)) s q (n) ≤ c 2 log q n.
This is best possible in that for all ε > 0 we have

s q (p(n)) s q (n) > (q -1 -ε) log q n infinitely often.
The proof of this result along with some useful preliminary results are given in Section 2.

For the minimal order of s q (p(n))/s q (n), Stolarsky treated the special case q = 2 and p(n) = n 2 . He proved that there are infinitely many integers n such that (4)

s 2 (n 2 ) s 2 (n) ≤ 4(log log n) 2 log n .
He conjectured that an analogous result is true for every fixed h ≥ 2 but he did "not see how to prove this".

Conjecture 1.2 (Stolarsky [14], 1978).

For fixed h ≥ 2, lim inf n→∞ s 2 (n h ) s 2 (n) = 0.
By naive methods, it can be quite hard to find even a single value n such that s 2 (n h ) < s 2 (n) for some h, let alone observe that the limit infimum goes to 0. For example, an extremely brute force calculation shows that the minimal n such that s 2 (n

3 ) < s 2 (n) is n = 407182835067 ≈ 2 39 .
In Section 3 we prove and generalize Conjecture 1.2.

Theorem 1.3. We have

lim inf n→∞ s q (p(n)) s q (n) = 0.
In view of our generalization, it is natural to ask how quickly we can expect this ratio to go to zero. Recall that h = deg p. Theorem 1.4. There exist explicitly computable constants B and C, dependent only on p(x) and q, such that for all ε with 0 < ε < h(4h+1) there exists an n < B • C 1/ε with s q (p(n))

s q (n) < ε.
The proof of this result along with an explicit construction for B and C is given in Section 4. As a nice Corollary to this result we have Corollary 1.5. There exists a constant C 0 , dependent only on p(x) and q, such that there exists infinitely many n with

s q (p(n)) s q (n) ≤ C 0 log n .
This is an improvement and generalization upon (4).

Proof. By solving for ε in n < B • C 1/ε , one easily sees that ε < log C log n-log B .
Without loss of generality we may assume that B > 1, hence we can take C 0 = log C.

One might expect that the ratio s q (p(n))/s q (n) is small only rarely, with most of its time being spent near h = deg p. It turns out that this ratio is small somewhat more often than expected.

Theorem 1.6. For any ε > 0 there exists an explicitly computable α > 0, dependent only on ε, p(x) and q, such that

# n < N : s q (p(n)) s q (n) < ε N α
where the implied constant also only depends on ε, p(x) and q.

The proof of this result is given in Section 5.

In Section 6 we collect together questions raised in this paper and pose some further lines of inquiry for this research.

Preliminaries and Proof of Theorem 1.1

First we prove some preliminary results about s q which we need in the proofs. Recall (cf. [START_REF] Lindström | On the binary digits of a power[END_REF]) that terms are said to be noninterfering if we can use the following splitting formulae:

Proposition 2.1. For 1 ≤ b < q k and a, k ≥ 1, s q (aq k + b) = s q (a) + s q (b), (5) s q (aq k -b) = s q (a -1) + (q -1)k -s q (b -1). (6)
Proof. Relation ( 5) is a consequence of the (strong) q-additivity of s q . For (6) we write b -

1 = k-1 i=0 b i q i with 0 ≤ b i ≤ q -1. Then s q (aq k -b) = s q ((a -1)q k + q k -b) = s q (a -1) + s q (q k -b) = s q (a -1) + s q k-1 i=0 (q -1 -b i )q i = s q (a -1) + k-1 i=0 (q -1 -b i ) implying (6).
Proposition 2.2. The function s q is subadditive and submultiplicative, i.e., for all a, b ∈ N we have s q (a + b) ≤ s q (a) + s q (b), [START_REF] Hare | The sum of digits of n and n 2[END_REF] s q (ab) ≤ s q (a)s q (b). ( 8)

Proof. The proof follows on the lines of [START_REF]On the bits counting function of real numbers[END_REF]Section 2]. As for [START_REF] Hare | The sum of digits of n and n 2[END_REF], an even stronger result is true, namely that s q (a + b) = s q (a) + s q (b) -(q -1) • r where r is the number of "carry" operations needed when adding a and b. Writing b = k-1 i=0 b i q i we also have

s q (ab) = s q a k-1 i=0 b i q i ≤ k-1 i=0 s q (ab i ) = k-1 i=0 s q (a + • • • + a b i times ) ≤ s(a) k-1 i=0 b i ,
where we used twice the subadditivity of s q and we get [START_REF] Lindström | On the binary digits of a power[END_REF].

Proof of Theorem 1.1. This is an almost direct generalization of Stolarsky's proof (see [START_REF] Stolarsky | The binary digits of a power[END_REF]Section 2]) and Propositions 2.1 and 2.2. First, suppose that p(n) has only nonnegative coefficients. Then using Proposition 2.2 we see that s q (p(n)) ≤ p(s q (n)). Therefore

s q (p(n)) s q (n) ≤ min{(q -1) log q p(n) + 1 , p(s q (n))} s q (n) ≤ c 1 • min{log q n, s q (n) h } s q (n) (9)
where c 1 only depends on p(x) and q. If log q n ≤ s q (n) h then we have (log q n) 1/h ≤ s q (n). From this and (9), we get that

s q (p(n)) s q (n) ≤ c 1 • log q n (log q n) 1/h = c 1 (log q n) 1-1/h .
Alternately, if log q n > s q (n) h then we have (log q n) 1/h > s q (n) and

s q (p(n)) s q (n) ≤ c 1 • s q (n) h-1 ≤ c 1 (log q n) 1-1/h .
For the lower bound, set

(10) k = log q (λ(h + 1)!) + 1,
where λ = max{a i : 0 ≤ i ≤ h}. By Stolarsky's use of the Bose-Chowla Theorem, there are infinitely many integers M ≥ 3(k + 1) such that there are integers y 1 , y 2 , . . . , y N with N := (M + 1)/(k + 1) -1, with the following three properties:

(i) 1 ≤ y 1 < y 2 < • • • < y N ≤ M h , (ii) y i ≡ 0 mod (k + 1), (iii)
all sums y j 1 + • • • + y j h are distinct (distinct sum property); here j 1 , j 2 , . . . , j h ∈ {1, 2, . . . , N } with possible repetition. Note that (iii) implies the distinct sum property for all

y j 1 + • • • + y j i with 1 ≤ i ≤ h. Now set n = N i=1 q y i , such that (11) p(n) = h i=0 a i n i = h i=0 a i α(i; h 1 , . . . , h N )q y 1 h 1 +•••+y N h N
where the summation is over all vectors (h 1 , . . . , h N ) satisfying [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF] as a polynomial in q. By the distinct sum property (iii) we have for all 0 [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF] are nonzero and bounded by ( 12)

h 1 + • • • + h N = i, and α(i; h 1 , . . . , h N ) denote the multinomial coefficients i!/(h 1 ! . . . h N !) bounded by i!. Consider
≤ i ≤ h that #{y 1 h 1 + • • • + y N h N : h 1 + • • • + h N = i} = N + i -1 N -1 .

Thus the coefficients of q y

1 h 1 +•••+y N h N = q R with h 1 + • • • + h N = h in (
a h h! + a h-1 (h -1)! + • • • + a 0 ≤ λ(h + 1)h! < q k .
By ( 12) and (ii), the sums

y 1 h 1 + • • • + y N h N ≡ 0 mod (k + 1
) and hence the powers q R are noninterfering and we get

s q (p(n)) s q (n) ≥ N + h -1 N -1 • 1 N ≥ N h-1 h! .
By construction,

log q n ≤ y N + 1 ≤ 2 h+1 N h (k + 1) h .
The claim now follows by observing that k is largest for q = 2. Secondly suppose that p(n) has at least one negative coefficient. Then the first claim follows by observing that s q (p(n)) ≤ log q p(n) +1 for sufficiently large n. For the lower bound, denote by a j the negative coefficient with smallest index j, i.e., a j < 0 and a j-l ≥ 0 for 1 ≤ l ≤ j. Then for all sufficiently large k we have

s q (p(q k )) = s q (a h q hk + • • • + a j+1 q (j+1)k + a j q jk + a j-1 q (j-1)k + • • • + a 0 ) = s q (a h q (h-j)k + • • • + a j+1 q k + a j ) + j-1 l=0 s q (a l ) ≥ k(q -1) -s(-a j -1) > k(q -1 -ε).
Here we have used Proposition 2.1. As s q (q k ) = 1 and log q (q k ) = k, the result follows. This completes the proof of Theorem 1.1.

Proof of Theorem 1.3

The proof of Theorem 1.3 will use a construction of a sequence with noninterfering terms. First assume that p(x) = x h , h ≥ 2 and define the polynomial

t m (x) = mx 4 + mx 3 -x 2 + mx + m
where m ∈ Z with m ≥ 3. By consecutively employing ( 5) and ( 6) we see that for all k with q k > m, [START_REF]On the bits counting function of real numbers[END_REF] s q (t m (q k )) = (q -1)k + s q (m -1) + 3s q (m).

The appearance of k in ( 13) is crucial. The next lemma lies at the heart of the proofs. We will use it to see that s q (t m (q k ) h ), h ≥ 2, is independent of k whenever k is sufficiently large. Furthermore, we will exploit the fact that the coefficients of [x i ] in t m (x) h are polynomials in m with alternating signs.

Lemma 3.1. For fixed h ≥ 2 and m ≥ 3, we have

t m (x) h = 4h i=0 c i,h (m) x i satisfying (14) 0 < c i,h (m) ≤ (2mh) h i = 0, 1, . . . , 4h.
In fact, we have

c 0,h (m) = c 4h,h (m) = m h , c 1,h (m) = c 4h-1,h (m) = hm h . ( 15
)
Proof. A direct calculation shows that t m (x) 2 and t m (x) 3 have property [START_REF] Stolarsky | The binary digits of a power[END_REF]

provided m ≥ 3. Set h = 2h 1 + 3h 2 with max(h 1 , h 2 ) ≥ 1. Then t m (x) h = t m (x) 2 . . . t m (x) 2 h 1 times • t m (x) 3 . . . t m (x) 3 h 2 times .
Since products of polynomials with all positive coefficients have all positive coefficients too, we get c i,h (m) > 0 for all i = 0, 1, . . . , 4h. On the other hand, the coefficients of t m (x) h are clearly bounded by the corresponding coefficients of the polynomial

m h (1 + x + x 2 + x 3 + x 4 ) h = m h 0≤l≤k≤j≤i≤h h i i j j k k l x i+j+k+l .
Therefore, for all i with 0 ≤ i ≤ 4h, we have

c i,h (m) ≤ m h 0≤l≤k≤j≤i≤h h! (h -i)!(i -j)!(j -k)!(k -l)! (16) ≤ m h h! exp(h -i + i -j + j -k + k -l) ≤ m h h!e h ≤ (2mh) h .
Proof of Theorem 1.3. Now let k be such that q k > (2mh) h . By ( 14) and ( 5) we then have

s q (t m (q k ) h ) = s q (c 0,h (m)) + s q (c 1,h (m)) + • • • + s q (c 4h,h (m))
where s q (c i,h (m)) is bounded by a function which only depends on q, m and h. Together with [START_REF]On the bits counting function of real numbers[END_REF] and letting k → ∞ we thus conclude for fixed m ≥ 3, lim k→∞ s q (t m (q k ) h )/s q (t m (q k )) = 0, as wanted.

Finally we consider the case with a general polynomial instead of x h . Write ( 17)

p(t m (x)) = a h t m (x) h + a h-1 t m (x) h-1 + • • • + a 1 t m (x) + a 0
where a h > 0 and h ≥ 2. First suppose that all the coefficients are nonnegative. Lemma 3.1 shows that for i with 2 ≤ i ≤ h all the coefficients of t m (x) i are positive. Also, the coefficient [

x 2 ] in p(t m (x)) is nonnegative if we choose m ≥ 3 sufficiently large. In fact, a sufficient condition is a h h 2 m h -hm h-1 ≥ a 1 which is true whenever (18) m ≥ 2a 1 h(3h -5)a h 1/(h-1)
.

If the polynomial p(x) has negative coefficients then there is a positive integer b such that the polynomial p(x + b) has all positive coefficients. A good choice for b is

(19) b = 1 + λ a h = 1 + λ a h , λ = max{|a i | : 0 ≤ i ≤ h}.
This is easy to see since both

p(x + b) -(a h (x + b) h -λ h-1 i=0 (x + b) i ) and a h (x + b) h -λ h-1 i=0 (x + b) i = a h - λ x + b -1 (x + b) h + λ x + b -1 = 1 x + b -1 (a h x + (b -1)a h -λ)(x + b) h + λ have nonnegative coefficients when b ≥ 1 + λ a h . Thus if q k > m + b then s q (t m (q k ) + b) = (q -1)k + s q (m
-1) + 2s q (m) + s q (m + b) and one similarly obtains for fixed m,

lim k→∞ s q (p(t m (q k ) + b))/s q (t m (q k ) + b) = 0.
This completes the proof of Theorem 1.3.

Proof of Theorem 1.4

The construction of an extremal sequence in the proof of Theorem 1.3 gives a rough bound on the minimal n such that s q (n h ) < s q (n). We first illustrate the method in the case q = 2, h = 3.

Set m = 3. Then for all k with 2 k > max 0≤i≤4h c i,h (m) = 225 we have

s 2 (t 3 (2 k )) = k + 1 + 6 = k + 7, s 2 (t 3 (2 k ) 3 ) = 2 • (4 + 3 + 4 + 4 + 4 + 4) + 4 = 50.
Therefore, by setting k = 44, we get min{n :

s 2 (n 3 ) < s 2 (n)} < 2 178 .
It is possible to show that the minimal such n to be n = 407182835067 ≈ 2 39 .

Proof of Theorem 1.4. Consider the general polynomial

p(x) = a h x h + a h-1 x h-1 + • • • + a 0 ∈ Z[x] with a h > 0, h ≥ 2. Let λ = max |a i |.
(x) + b) ∈ Z[x].
To begin with, we estimate the coefficient of

x i , 0 ≤ i ≤ h of p(x + b), ( 20
) h j=i a j b j-i j i ≤ h j=i a j b j-i j i ≤ λ(2b) h .
Combining (20) with (15), we find that the constant term of p(t m (x)+b) is bounded by

λ(2b) h h i=0 m i = λ(2b) h m h+1 -1 m -1 ≤ λh(4mbh) h
since m ≥ 3 and h ≥ 2. Again from (20) and ( 14), we find that the other coefficients of p(t m (x) + b) are bounded by

(21) λ(2b) h h i=1 (2mi) i ≤ λh(4mbh) h .
Therefore the coefficients of p(t m (x) + b) are bounded by λh(4mbh) h . Hence for q k > m + b, we have

(22) s q (p(t m (q k )) + b) ≤ (q -1)(4h + 1) log(λh(4mbh) h ) log q + 1 .
On the other hand, we clearly have s q (t m (q k ) + b) > (q -1)k for

q k > m + b. Let k = 4h + 1 ε log(λh(4mbh) h ) log q + 1 + 1.
Then for 0 < ε < h(4h + 1) we have q k > m + b and hence

s q (p(t m (q k ) + b)) s q (t m (q k ) + b) < ε.
Therefore, min n :

s q (p(n)) s q (n) < ε ≤ t m (q k ) + b < m(q 4k + q 3k + q k + 1) < 2mq 4k ≤ 2mq 4 qλh(4mbh) h (16h+4)/ε .
Setting B := 2mq 4 and C := qλh(4mbh) h 16h+4 , it gives the desired result.

Proof of Theorem 1.6

We start our analysis with the simple case of p

(n) = n h . Let t m (x) = mx 4 + mx 3 -x 2 + mx + m as in Section 3. Letting n = n k,m = t m (q k )
we see from equation ( 13) that, for m < q k , s q (n) = (q -1)k + s q (m -1) + 3s q (m) ≥ (q -1)k.

If m has i q-ary digits then n will have 4k + i q-ary digits. We see that t m (q k ) h is of length at most h(4k + i).

Let t m (q k ) h = 4h j=0 c j q kj . These c j are dependent upon m and h, but are independent of k for k sufficiently large. We see from equation ( 16) that c j ≤ (mh • 2) h and hence has at most hi + h log q h + h q-ary digits. As there are (4h+1) coefficients c j and s q (c j ) ≤ (q-1)(hi+h log q h+h), we get s q (n h ) ≤ (q -1)(4h + 1) hi + h log q h + h .

Combining these together we have

s q (n h ) s q (n) ≤ (q -1)(4h + 1) hi + h log q h + h (q -1)k = (4h + 1) hi + h log q h + h k .
Without loss of generality suppose that 0 < ε < h(4h + 1). Let k 0 be large enough so that k 0 > i and (4h + 1) hi + h log q h + h k 0 < ε.

For i sufficiently large, we can take k 0 = (4h+1)(hi+i) ε . Then this says that for every sufficiently large m having i q-ary digits, there is an integer n having 4k 0 + i q-ary digits such that

s q (n h ) s q (n) < ε.
Moreover, by construction, each distinct m will give rise to a distinct n. Letting

α = i 4k 0 + i ≥ i 4(4h + 1)(h + 1)i/ε + i = ε 4(4h + 1)(h + 1) + ε we get as N → ∞ that # n < N : s q (n h ) s q (n) < ε N α .
Now to extend this for general p(x), we proceed as we did in the proof of Theorem 1.3. First consider the case where p(x) has only nonnegative coefficients. There is a lower bound on m such that p(t m (x)) will have only nonnegative coefficients and we proceed as before, after which the result follows as before. Second, if p(x) has at least one negative coefficient, then consider instead the polynomial p(x + b) for sufficiently large b, which will have only nonnegative coefficients, and the result follows.

Conclusions and further work

All results in this paper have explicitly computable constants for existence or density results. Many times these constants are far from the observed experimental values, and it is quite likely that many of them may be strengthened. Examples include Theorems 1.4 and 1.6. Some obvious generalizations of this problem are in looking at the ratios of s q (p 1 (n))

sq(p 2 (n)) , or even more generally of

s q 1 (p 1 (n))
sq 2 (p 2 (n)) with respect to two different bases q 1 , q 2 . Alternately, instead of looking at polynomials p(x) ∈ Z[x], we could look at quasi-polynomials p(n) with p(x) ∈ R[x].

As another direction, we could consider expansions in other numeration systems, e.g. the Zeckendorf expansion (or expansions with respect to linear recurrences) or the balanced based q representation. In the latter case, for example, 11 = 1•3 2 +1•3 1 -1•3 0 , and s 3 (11) = 1+1-1 = 1, being the sum-of-digits function in this representation. This value will quite often be 0, but its extremal distribution could still have some interesting properties.

Theorem 1 . 1 .

 11 Let p(x) ∈ Z[x] have degree at least 2 and positive leading coefficient.

  Pick b such that p(x+b) has only nonnegative coefficients, as in (19). Pick m ≥ 3 such that p(t m (x) + b) has only nonnegative coefficients, as in (18). Our task is to bound the coefficients of of p(t m

Acknowledgements.

The authors thank J. Shallit for his remarks on a previous version of this paper.

K.G. Hare was partially supported by NSERC. Computational support provided by CFI/OIT grant. Th. Stoll was partially supported by an APART grant of the Austrian Academy of Sciences.


Kevin G Hare
email: kghare@math.uwaterloo.ca

Shanta Laishram
email: shanta@isid.ac.in

Thomas Stoll
email: stoll@iml.univ-mrs.fr

THE SUM OF DIGITS OF n AND n 2

Let s q (n) denote the sum of the digits in the q-ary expansion of an integer n. In 2005, Melfi examined the structure of n such that s 2 (n) = s 2 (n 2 ). We extend this study to the more general case of generic q and polynomials p(n), and obtain, in particular, a refinement of Melfi's result. We also give a more detailed analysis of the special case p(n) = n 2 , looking at the subsets of n where s q (n) = s q (n 2 ) = k for fixed k.

Introduction

Let q ≥ 2 and denote by s q (n) the sum of digits in the q-ary representation of an integer n. Recently, considerable progress has been made towards understanding the interplay between the sum-of-digits of some algebraically defined sequences, such as primes [START_REF] Mauduit | Sur un probléme de Gelfond: la somme des chiffres des nombres premiers[END_REF] and polynomials [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF] or, in particular, squares [START_REF] Mauduit | La somme des chiffres des carrés[END_REF]. In the latter, C. Mauduit and J. Rivat proved an asymptotic expansion of the sum of digits of squares [START_REF] Mauduit | La somme des chiffres des carrés[END_REF] in arithmetic progressions. Their proof heavily relies on good estimates of quadratic Gauss sums. For the case of general polynomials p(n) of degree h > 2 there is still a great lack of knowledge regarding their distribution with respect to digitally defined functionals [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF].

Several authors studied the pointwise properties and relationships of s q (p(n)), e.g., K. Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF], B. Lindström [START_REF] Lindström | On the binary digits of a power[END_REF], G. Melfi [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF], and M. Drmota and J. Rivat [START_REF] Drmota | The sum-of-digits function of squares[END_REF]. In particular, a conjecture of Stolarsky [START_REF] Stolarsky | The binary digits of a power[END_REF] about some extremal distribution properties of the ratio s q (p(n))/s q (n) has been recently settled by the authors [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF]. Melfi [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF] proposed to study the set of n's such that s 2 (n 2 ) = s 2 (n), and he obtained that [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF] # n < N :

s 2 (n 2 ) = s 2 (n) N 1/40 .
Using heuristic arguments, Melfi conjectured a much stronger result that

(2) # n < N : s 2 (n 2 ) = s 2 (n) ≈ N β log N with β ≈ 0.75488 . . . , giving an explicit formula for β. The aim of the present paper is to provide a generalization to general p(n) and base q of Melfi's result as well as to use the method of proof to sharpen Melfi's exponent in [START_REF] Dartyge | Congruences de sommes de chiffres de valeurs polynomiales[END_REF]. Moreover, we provide a local analog, i.e., getting a lower bound for the number of n's such that s q (n 2 ) = s q (n) = k for some fixed k.

Theorem 1.1. Let p(x) ∈ Z[x] have degree at least 2, and positive leading coefficient. Then there exists an explicitly computable γ > 0, dependent only on q and p(x), such that

(3) # n < N, q n : |s q (p(n)) -s q (n)| ≤ q -1 2 N γ ,
where the implied constant depends only on q and p(x).

This result is given in Section 2. In the general case of q-ary digits and polynomials p(x), the bound (q -1)/2 in (3) cannot be improved. This is easily seen by recalling the well-known fact [START_REF] Lindström | On the binary digits of a power[END_REF] s q (n) ≡ n mod (q -1).

Indeed, if we set p(x) = (q -1)x 2 + x + a for a ∈ N then we find that

s q (p(n)) -s q (n) ≡ p(n) -n ≡ a mod (q -1)
which could be any of 0, 1, . . . , q -2 depending only on the choice of a.

The method of proof of Theorem (1.1) allows to improve on Melfi's result (1). Theorem 1.2.

(5)

# n < N :

s 2 (n 2 ) = s 2 (n) N 1/19 .
Following on Melfi's paper [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF], we examine the case when p(n) = n 2 and q = 2 in more detail. We consider the set of all n's such that s 2 (n) = s 2 (n 2 ), and partition the set into the subsets dependent upon the value of s 2 (n). By noticing that s 2 (n) = s 2 (2n) and s 2 (n 2 ) = s 2 ((2n) 2 ) we see that we can restrict our attention to odd n.

Theorem 1.3. Let k ≤ 8. Then {n odd : s 2 (n 2 ) = s 2 (n) = k} is a finite set.
This was done by explicit computation of all such n which are given in Tables 1 and2. A discussion of how these computations were made is given in Section 3.

Based on these initial small values of k, one might expect that this is always true. Let [START_REF] Mauduit | La somme des chiffres des carrés[END_REF] n 2 = 1101111 00 . . . 00 r 1101111 be written in base 2. Then s 2 (n) = s 2 (n 2 ) = 12 for all r ≥ 8. This is in fact a special case of a more general property.

Theorem 1.4. Let k ≥ 16 or k ∈ {12, 13}. Then {n < N, n odd : s 2 (n 2 ) = s 2 (n) = k} is an infinite set.
The proof of this result is given in Section 4. Despite of great effort we are not able to decide the finiteness problem in the remaining cases k ∈ {9, 10, 11, 14, 15}. However, we will comment on some heuristic evidence that it seems unlikely that there are infinitely many solutions in the cases k = 9 and k = 10, respectively, in Section 5.

Somewhat surprisingly, a similar answer can be given if q ≥ 3.

Theorem 1.5. Let q ≥ 3 and assume k ≥ 94(q -1).

Then the equation

(7) s q (n 2 ) = s q (n) = k
has infinitely many solutions in n with q n if and only if

(8) k(k -1) ≡ 0 mod (q -1).
We show this result in Section 6.

2. Proof of Theorems 1.1 and 1.2

Following Lindström [START_REF] Lindström | On the binary digits of a power[END_REF] we say that terms are noninterfering if we can use the following splitting formulae: Proposition 2.1. For 1 ≤ b < q k and a, k ≥ 1, s q (aq k + b) = s q (a) + s q (b), (9)

s q (aq k -b) = s q (a -1) + (q -1)k -s q (b -1). ( 10
)
Proof. See [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF].

Proof of Theorem 1.1: The proof uses a construction of a sequence with noninterfering terms which has already been used in [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF]. However, to obtain the bound N γ in (3) instead of a logarithmic bound, we have to make a delicate refinement. To begin with, define the polynomial

t m (x) = mx 4 + mx 3 -x 2 + mx + m
where m ∈ Z. Set m = q l -r with 1 ≤ r ≤ q αl , q r and 0 < α < 1. Obviously, for α < 1 there exists l 0 (α) such that for all l > l 0 (α) we have m ≥ 3. Furthermore let k be such that q k > m. By consecutively employing (9) and (10) we see that s q (t m (q k )) = (q -1)k + s q (m -1) + 3s q (m) = (q -1)k + s q (q l -(r + 1)) + 3s q (q l -r) = (q -1)k + (q -1)l -s q (r) + 3((q -1)l -s q (r -1)) (11) = (q -1)k + 4(q -1)l -K(q, r)

where K is depends only on q and r, and does not depend on k. First consider the easier case of monomials p(n) = n h , h ≥ 2 where we can give a somewhat more direct proof. We have

t m (x) h = (mx 4 + mx 3 -x 2 + mx + m) h = 4h j=0 c j,h (m)x j (12) = m h x 4h + hm h x 4h-1 + h 2 m h -hm h-1 x 4h-2 + h + h 3 m h -2 h 2 m h-1 x 4h-3 + smaller powers.
From [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF]Lemma 3.1] we have that t m (x) h has only positive coefficients and 0 < c j,h (m) ≤ (2mh) h . This means that s q (t m (q k ) h ) does not depend on k if k is sufficiently large (see ( 9)). More precisely, if q k > (2mh) h (which is true if q k > (2h) h q lh , or equivalently if k > (h+1)l for sufficiently large l), then by a symmetry argument for the coefficients of t m (x) h ,

s q (t m (q k ) h ) ≥ 2 s q (m h ) + s q (hm h ) + s q h 2 m h -hm h-1 +s q h + h 3 m h -2 h 2 m h-1 . ( 13
)
Consider the first summand s q (m h ) in (13). We have

m h = (q l -r) h = h j=0 h j (-1) h-j q jl r h-j = h j=0 (-1) h-j d j q jl (14)
which shows that m h is a polynomial in q l with coefficients of alternating signs. Now there are exactly h/2 negative signs in this expansion. All coefficients in (14) are bounded in modulus by

(15) 0 < d j ≤ (2r) h ≤ (2q αl ) h ≤ q (αl+1)h ,
and in turn their q-ary sum of digits is less than s q (d j ) ≤ (q-1)(αl+1)h. (Note if equality is strict in (15) then s q (d j ) = 1, otherwise it will have at most (αl+1)h digits.) Therefore, by using (10), for h/2 times, and observing that s q (d j ) ≤ (q -1)(αl + 1)h we get that for fixed α < 1/h and sufficiently large l we have

s q (m h ) ≥ h/2 (q -1)l -h/2 (q -1)(αl + 1)h ≥ h 2 (q -1)(l(1 -αh) -h). (16)
A similar argument can be applied to the other three summands in (13). This yields

(17) s q (t m (q k ) h ) ≥ 4h(q -1)(l(1 -αh) -h).
We recall that s q (t m (q k ) h ) is independent of k (see discussion after (12), whereas from (11) we have s q (t m (q k )) will increase by q -1 for each increase in k. Take α = 1/(5h 2 ). Note that h ≥ 2 and take k and l sufficiently large so that

k + 4h 2 ≤ 4l 5h -6 5
and

(h + 1)l < k
The second requirement is necessary for the validity of equation ( 17). This then implies that

k + 4h 2 ≤ 4l 5h-6 5 =⇒ k ≤ 4hl 1 -1 5h -1 h -4h 2 =⇒ k + 4l ≤ 4hl(1 -αh) -4h 2 =⇒ (q -1)k + 4(q -1)l -K(q, r) ≤ 4h(q -1)(l(1 -αh) -h) =⇒ s q (t m (q k )) ≤ s q (t m (q k ) h )
Recall that for each increase of k by 1, the left hand side will increase by q -1, (by (11)), and the right hand side will remain fixed. Hence, for l sufficiently large, we can find a k ≥ k such that

(18) |s q (t m (q k ) h ) -s q (t m (q k ))| ≤ q -1 2 .
Summing up, we have obtained that for sufficiently large l we can find q αl values r where we in turn can provide a value k satisfying (18). In addition, each triple (l, r, k) gives rise to a different value of t m (q k ). We thus have [START_REF] Hare | Stolarsky's conjecture and the sum of digits of polynomial values[END_REF]. Now consider the case of a general polynomial p

(x) = a h x h +a h-1 x h-1 + • • • + a 0 ∈ Z[x].
There exist positive integers s 1 and s 2 , both only depending on the polynomial p(x) such that

p(q s 1 x + q s 2 + 1) = a h x h + a h-1 x h-1 + • • • + a 0
has only positive coefficients. With the notation of (12) we obtain

p(q s 1 t m (x) + q s 2 + 1) = 3 i=0 a h c 4h-i,h (m) x 4h-i (19) + 7 i=4 a h c 4h-i,h (m) + a h-1 c 4h-i,h-1 (m) x 4h-i + smaller powers.
First suppose h ≥ 4. By choosing s 1 sufficiently large (this choice again only depends on p(x)) we get that the coefficients of x j in p(q s 1 t m (x) + q s 2 + 1) with 4h -7 ≤ j ≤ 4h are polynomials in m of degree h since we can avoid unwanted cancellation for these coefficients. The coefficients of these terms (as polynomials in m) are alternating in sign, since for h ≥ 4 and i = 0, 1, . . . , 2h -1 we have

c i,h (m) = c 4h-i,h (m) = h j=h-i/2 d j,i,h m j (20)
where d j,i,h d j+1,i,h < 0 for all j with h -i/2 ≤ j < h. Setting m = q l -r we therefore can choose s 1 , s 2 in the way that a h c 4h-i,h (m)+ a h-1 c 4h-i,h-1 (m) as a polynomial in q l has h/2 negative coefficients for each = 0, 1, . . . , 2h -1. Now, for q s 2 + 1 < q s 1 , we get by (11) that s q (q s 1 t m (q k ) + q s 2 + 1) ≤ (q -1)k + 4(q -1)l + 2.

In (19) we have therefore found eight summands sharing the property of the eight summands in the monomial case (see ( 13)). From this we proceed as in the case of monomials to get the statement.

It remains to deal with the cases of general quadratic and cubic polynomials, where we cannot directly resort to (20) (note that 8 > (2h -1) + 1 for h = 2, 3). We instead do a more direct calculation. Let h = deg p = 2 which is the case of quadratic polynomials. By suitably shifting the argument x → q s 1 x + q s 2 + 1 we can arrange for a polynomial p(q s 1 x + q s 2 + 1) = a 2 x 2 + a 1 x + a 0 with a 2 , a 1 , a 0 > 0 and 2a 2 > a 1 . Each coefficient of x i in p(q s 1 t m (x) + q s 2 + 1), 0 ≤ i ≤ 8, is a function of m and of a 2 , a 1 and a 0 . In a similar way as before (here we use 9 summands instead of the 8 in the case of h ≥ 4) we obtain for sufficiently large l, s q (p(q s 1 t m (q k ) + q s 2 + 1)) > 8(q -1)l ≥ 4h(q -1)l. Now we can choose k suitably to get the assertion. Finally, for a cubic polynomial, we are able to achieve p(q s 1 x + q s 2 + 1) = a 3 x 3 + a 2 x 2 + a 1 x+a 0 with a 3 , a 2 , a 1 , a 0 > 0 and 3a 3 > a 2 . Then, each coefficient of x i in p(q s 1 t m (x) + q s 2 + 1), 0 ≤ i ≤ 12, is a function of m and a 3 , a 2 , a 1 , a 0 , and thus we get for sufficiently large l, s q (p(q s 1 t m (q k ) + q s 2 + 1)) > 12(q -1)l ≥ 4h(q -1)l.

By choosing k suitably, we obtain the result. This completes the proof of Theorem 1.1.

Proof of Theorem 1.2: We apply the method of proof of Theorem 1.1 to the special case q = 2 and p(n) = n 2 . Instead of using the rather crude bounds, we here use exact values to get our result. To begin with, we observe that the largest coefficient (as m → ∞) of t m (x) 2 is the coefficient of x 4 , namely 4m 2 +1. Therefore we get noninterfering terms when

2 k > 4m 2 +1. A sufficient condition for this is 2 k ≥ 4•2 2l = 2 2l+2 , or equivalently, (21) k ≥ 2l + 2.
On the other hand, the coefficients of x 8 and x 7 (resp. x 1 and x 0 ) in t m (x) 2 are m 2 and 2m 2 which have the same binary sum of digits. Now assume α < 1/2 and l > l 0 (α) be sufficiently large. We then use Proposition 2.1 and set m = 2 l -r with 1 ≤ r ≤ 2 αl to obtain

s 2 (t m (2 k ) 2 ) ≥ 4s 2 (m 2 ) + s 2 (4m 2 + 1) (22) = 5s 2 (2 l-1 -r)2 l+1 + r 2 + 1 ≥ 5s 2 (2 l-1 -r) = 5 ((l -1) -s 2 (r -1)) ≥ 5(l -1) -5αl ≥ (2 + ε)l
for any 0 < ε < 1/2. This means that for any α < 1/2 we have q αl values r where we in turn can provide a value k satisfying (18) which is due to 2l

+ 2 ≤ k ≤ (2 + ε)l.
This yields t m (q k ) ≤ 2q 4k+l ≤ 2q 4(2+ε)l+l ≤ q (9+5ε)l .

Hence, letting N = q (9+5ε)l we note that we have

q αl = N 1 (9+5ε)l αl = N α/(9+5ε) ≥ N 1/19
solutions to (18). This finishes the proof.

Proof of Theorem 1.3

The proof that there is only a finite number of odd n such that s 2 (n 2 ) = s 2 (n) ≤ 8 is a strictly computational one. We discuss how our algorithm works.

Consider

n = k i=1 2 r i = 2 r 1 + 2 r 2 + • • • + 2 r k with 0 = r 1 < r 2 < r 3 < • • • < r k . We have n 2 = k i=1 k j=1 2 r i +r j = k i=1 2 2r i + k i=1 k j=i+1 2 r i +r j +1 .
We therefore need to examine the exponents

{2r 1 , 2r 2 , . . . , 2r k , r 1 + r 2 + 1, r 1 + r 3 + 1, . . . , r k-1 + r k + 1}
and the possible iterations between these exponents by carry propagation.

Clearly, 2r 1 is the strict minimum within these exponents. Other relationships between exponents are not as clear. For example, r 1 + r 3 + 1 could be less than, equal to, or greater than 2r 2 depending on the choices of r 3 and r 2 . Each of these cases must be examined in turn. Numerous of these inequalities have implications for the order of other exponents in the binary expansion of n 2 . So, once we make an assumption in our case by case analysis, this might rule out future possibilities. For example, if we assume that 2r 3 < 1 + r 1 + r 4 , then we have as a consequence that 1 + r 2 + r 3 < 1 + r 1 + r 4 (by noticing that r 2 < r 3 ). In the case of equality we "group" terms. For example, if we assumed that 2r 3 = 1 + r 2 + r 4 , then we could, first, replace all occurrences of r 2 with 2r 3 -1 -r 4 , and second replace 2 2r 3 + 2 1+r 2 +r 4 by 2 2r 3 +1 .

Our algorithm occasionally finds a solution set with fractional or negative values for r i , which is a contradiction. On the other hand, it is possible for the algorithm to find a solution, even if all of the exponents cannot be explicitly determined. This would happen if there is an infinite family of n with s 2 (n 2 ) = s 2 (n) = k with some nice structure, (as is the case for k = 12, see ( 6)). The algorithm will detect, and report this. We used the method for k up to 8. For each of these values, there was only a finite number of n, and all of them are enumerated in Tables 1 and2.

Proof of Theorem 1.4

For the proof of Theorem 1.4, we first state some auxiliary results. Denote by (n) 2 the binary representation of n, and 1 (k) a block of k binary 1. We begin with the following key observation. Proposition 4.1. If there exists u and v such that s 2 (u) + s 2 (v) = s 2 (u 2 ) + s 2 (uv) + s 2 (v 2 ) = k, then for i sufficiently large, the numbers of the form (n

) 2 = u0 i v satisfy s 2 (n 2 ) = s 2 (n) = k.
Proof. This follows at once from Proposition 2.1, relation (9).

Base 10 Base 2

Base 10 Base 2

s 2 (n) = s 2 (n 2 ) = 1 s 2 (n) = s 2 (n 2 ) =
(n 2 ) = s 2 (n) ≤ 7.
We use Proposition 4.1 to prove the following lemma.

Lemma 4.2. Let (u) 2 = 1 (k 1 ) 01 (n 1 ) and (v) 2 = 1 (k 2 ) 01 (n 2 ) . Assume that n 1 ≥ k 1 + 2, n 2 ≥ k 2 + 2 and n 1 ≥ n 2 . Then s 2 (u 2 ) = n 1 and s 2 (v 2 ) = n 2 ,
Base 10 Base 2 Base 10 Base 2

s 2 (n) = s 2 (n 2 ) = 8 s 2 (n) = s 2 (n 2 ) = 8 (
(n 2 ) = s(n) = 8.
and

s 2 (uv) =      k 1 + 2 if n 2 = k 1 + 1, n 1 = n 2 + k 2 + 1 n 2 + 1 if n 2 > k 1 + 1, n 1 = n 2 + k 2 + 1 n 1 + 1 if k 1 = k 2 , n 1 > n 2 .
Proof. Let (U ) 2 = 1 (k) 01 (n) with n ≥ k+2. Then U = 2 n -1+2 n+1 (2 k -1) and we calculate

U 2 = 2 2n -2 n+1 + 1 + 2 n+2 (2 n+k -2 n -2 k + 1) + 2 2n+2 (2 2k -2 k+1 + 1) = 1 + 2 n+1 + 2 2n + 2 n+k+2 (1 + 2 + 2 2 + • • • + 2 n+k-1 ) -2 2n+k+2 = 1 + 2 n+1 + 2 n+k+2 + • • • + 2 2n-1 + 2 2n+k+2 + 2 2n+k+3 + • • • + 2 2n+2k+1 .
Hence s 2 (U 2 ) = n and therefore s 2 (u 2 ) = n 1 and s 2 (v 2 ) = n 2 . Now, consider s 2 (uv). We have

uv =1 + 2 n 1 + 2 n 2 + 2 n 1 +n 2 -2 n 1 +k 1 +1 -2 n 2 +k 2 +1 -2 n 1 +n 2 +k 1 +1 - 2 n 1 +n 2 +k 2 +1 + 2 n 1 +n 2 +k 1 +k 2 +2 .
We may assume that k 1 ≥ k 2 . Then

W := 2 n 1 +n 2 +k 1 +k 2 +2 -2 n 1 +n 2 +k 2 +1 -2 n 1 +n 2 +k 1 +1 = 2 n 1 +n 2 +k 2 +1 (1 + 2 + • • • + 2 k 1 -k 2 -1 + 2 k 1 -k 2 +1 + • • • + 2 k 1 )
has s 2 (W ) = k 1 . We distinguish three cases to conclude:

(1) Let

n 1 = n 2 + k 2 + 1 and n 2 = k 1 + 1. Then uv = 1 + 2 n 2 + W and hence s 2 (uv) = k 1 + 2. (2) Let n 1 = n 2 + k 2 + 1 and n 2 > k 1 + 1. Then uv = 1 + 2 n 2 + W + 2 n 1 +k 1 +1 (2 n 2 -k 1 -1 -1) and hence s 2 (uv) = 2 + k 1 + n 2 -k 1 -1 = n 2 + 1. (3) Let k 1 = k 2 = k and n 1 > n 2 . Then uv = 1 + 2 n 2 + 2 n 1 + W + 2 n 2 +k+1 (2 n 1 -k-1 -1) -2 n 1 +k+1 and hence s 2 (uv) = 3 + k + n 1 - k -2 = n 1 + 1. This finishes the proof. Proof of Theorem 1.4. Let n 1 , n 2 , k 1 , k 2 be positive integers with n 1 ≥ k 1 + 2, n 2 ≥ k 2 + 2 and u, v be as in Lemma 4.2. Let (N ) 2 = u0 R v be the binary representation of N where R ≥ n 1 + n 2 + k 1 + k 2 . By Proposition 4.1 and Lemma 4.2 we have for any R ≥ n 1 + n 2 + k 1 + k 2 , s 2 (N ) = s 2 (u) + s 2 (v) = n 1 + n 2 + k 1 + k 2 , s 2 (N 2 ) = s 2 (u 2 ) + s 2 (v 2 ) + s 2 (uv) = n 1 + n 2 + s 2 (uv). Let k ≥ 2. Taking k 1 = k 2 = k and n 1 = n 2 = 2k, we find from Lemma 4.2 and 2k ≥ k + 2 that s 2 (N 2 ) = s 2 (N ) = 6k
implying there are infinite families of n such that s 2 (n) = s 2 (n 2 ) = s for s of the form 6k with k ≥ 2.

Let

k 2 = 2, k 1 ≥ 3, n 2 = k 1 + 2 and n 1 = n 2 + k 2 + 1 = k 1 + 4. Then s 2 (uv) = n 2 +1 by Lemma 4.2 implying s 2 (N 2 ) = s 2 (N ) = 3(k 1 +2)+1.
Hence there are infinite families of n such that s 2 (n) = s 2 (n 2 ) = s for s of the form 3k + 1 with k ≥ 5.

Let

k 1 ≥ k 2 ≥ 3 and n 2 = k 1 + k 2 -1, n 1 = n 2 + k 2 + 1. Then s 2 (uv) = n 2 + 1 = k 1 + k 2 from Lemma 4.2 implying s 2 (N 2 ) = s 2 (N ) = 3k 1 + 4k 2 -1. Let k 2 = 3. Then s 2 (N 2 ) = s 2 (N ) = 3(k 1 + 3) + 2 for k 1 ≥ 3 giving infinite families of n such that s 2 (n) = s 2 (n 2 ) = s for s of the form 3k + 2 with k ≥ 6. Let k 2 = 4. Then s 2 (N 2 ) = s 2 (N ) = 3(k 1 + 5) for k 1 ≥ 4 giving infinite families of n such that s 2 (n) = s 2 (n 2 ) =

Evidence that s

2 (n 2 ) = s 2 (n) ≤ 10 is finite
All examples of infinite families with s 2 (n 2 ) = s 2 (n) = k have the form given from Lemma 4.1. We show that there do not exists u and v satisfying Proposition 4.1, with k ∈ {9, 10}. We illustrate this method for k = 8, as it contains all of the key ideas without being overly cumbersome. The case of k = 8 is actually proved to be finite by the techniques of Section 3, but this does not detract from this example. The other two cases are similar.

Assume the contrary, that there exists u and v such that

s 2 (u) + s 2 (v) = s 2 (u 2 ) + s 2 (v 2 ) + s 2 (uv) = 8
We easily see that s 2 (v), s 2 (u) ≥ 2. Furthermore, as s 2 (u), s 2 (v) ≥ 2, we see that s 2 (u 2 ), s 2 (v 2 ) ≥ 2. Also, we have that s 2 (uv) ≥ 2. Therefore, we have 2 ≤ s 2 (u 2 ), s 2 (v 2 ) ≤ k -4. Lastly, we see that one of u or v must be "deficient", that s 2 (u 2 ) < s 2 (u) or s 2 (v 2 ) < s 2 (v). Assume without loss of generality that s 2 (u 2 ) < s 2 (u). Given the restrictions, we have that 2 ≤ s 2 (u) ≤ 6. Using the same algorithm as in Section 3, we can find all u such that 2 ≤ s 2 (u) ≤ 6 and s 2 (u 2 ) < s 2 (u), s 2 (u 2 ) ≤ 4. These are the first three entries of Table 3.

Therefore, it suffices to show that there do not exists v for u = 23, 47 or 111 with s 2 (u) + s 2 (v) = s 2 (u 2 ) + s 2 (v 2 ) + s 2 (uv) = 8.

(1) Let u = 23 = 10111. Given that s 2 (uv) ≥ 2 we have that s 2 (v) = 4 and s 2 (v 2 ) ≤ 3. The only possible solution by (3) Let u = 111 = 11101111. Given that s 2 (uv) ≥ 2 we have that s 2 (v) = 2 and s 2 (v 2 ) ≤ 2. There is one possible solution to this by Table 3, namely v = 3 = 11. But then s 2 (uv) = 5, a contradiction. A similar, but more elaborate analysis can be done for k = 9 and k = 10 using the additional information in Table 3. Here we look at 2 ≤ s 2 (u) ≤ 7, s 2 (u 2 ) < s 2 (u) and s 2 (u 2 ) ≤ 5.

Proof of Theorem 1.5

The proof uses the strategy adopted for the case q = 2 (see Section 3). However, in order to handle more possible digits in the case of q ≥ 3, the analysis is much more delicate. In the proof we will make frequent use of the fact (4) and of the splitting formulae of Proposition 2.1, which will apply if we have noninterfering terms at our disposal.

To begin with, the condition ( 8) is necessary, since (7) implies

s q (n 2 ) -s q (n) ≡ n 2 -n ≡ k 2 -k ≡ 0 mod (q -1).
For the construction of an infinite family, we first prove a crucial lemma.

Lemma 6.1. Let u = ((q -1) k 0 (q -1) n e) q with k ≥ 2, n ≥ k + 2 and 0 ≤ e ≤ q -2. Then s q (u) = (q -1)(n + k) + e and s q (u 2 ) = (q -1)(n + 1) + f (q, e) where (23) f (q, e) = s q ((q -e) 2 ) + s q (2(q -1)(q -e)) -s q (2(q -e) -1).

Proof. Since u = e + (q n -1)q + (q k -1)q n+2 , we get u 2 = (q -e) 2 + 2(q -1)(q -e)q n+1 -2(q -e)q n+k+2

+ (q -1) 2 q 2n+2 -2(q -1)q 2n+k+3 + q 2n+2k+4 . (24)

By assumption that n ≥ k + 2 and n, k ≥ 2, the terms in (24) are noninterfering. We therefore get s q (u 2 ) = s q ((q -e) 2 ) + s q (2(q -1)(q -e)) -s q (2(q -e) -1) + (n -k)(q -1) + s q ((q -1) 2 -1) -s q (2(q -1) -1) + (k + 1)(q -1). = (n + 1)(q -1) + s q (q 2 -2q) -s q (2q -3) + f (q, e).

The claimed value of s q (u 2 ) now follows by observing that s q (q 2 -2q) = s q (q -2) = q -2 and s q (2q -3) = s q (q + q -3) = 1 + q -3 = q -2. Now consider u = ((q -1) k 1 0 (q -1) n 1 ) q , v = ((q -1) k 2 0 (q -1) n 2 e) q where we suppose k 1 , n 1 , k 2 , n 2 ≥ 2 and n 1 ≥ k 1 + 2, n 2 ≥ k 2 + 2. Since q n we further suppose that e = 0. We want to construct an infinite family of solutions to [START_REF] Melfi | On simultaneous binary expansions of n and n 2[END_REF] of the form n = (u0 (i) v), where i is a sufficiently large integer, such that terms will be noninterfering. Our task is to find an admissible set of parameters k 1 , n 1 , k 2 , n 2 such that for sufficiently large n 1 + n 2 + k 1 + k 2 we have s q (u) + s q (v) = s q (u 2 ) + s q (2uv) + s q (v 2 ) = e + (q -1)(n

1 + n 2 + k 1 + k 2 ). ( 25
)
First it is a straightforward calculation to show that 2uv = w 1 + w 2 with (26) w 1 = 2q n 1 +n 2 +k 1 +k 2 +3 -2(q -1)q n 1 +n 2 +k 1 +2 -2(q -1)q n 1 +n 2 +k 2 +2 and w 2 = 2(q -1) 2 q n 1 +n 2 +1 -2(q -e)q n 1 +k 1 +1 -2q n 2 +k 2 +2 + 2(q -1)(q -e)q n 1 + 2(q -1)q n 2 +1 + 2(q -e). (27) Note that w 1 and w 2 are noninterfering because of k 2 ≥ 2. Now, set (28)

k 1 = n 2 ≥ k 2 + 2, n 1 = 2k 2 -α,
where we will later suitably choose α = α(q, e) only depending on q and e. Then terms in (26) are again noninterfering and we get s q (w 1 ) = s q (2q k 1 +1 -2(q -1)q k 1 -k 2 -2(q -1))

= s q (2q k 2 +1 -2q + 1) + (q -1)(k 1 -k 2 ) -s q (2q -3) = 1 + k 2 (q -1) + (q -1)(k 1 -k 2 ) -(q -2) = (k 1 -1)(q -1) + 2.

Next, by (28), we find that w 2 = 2q k 1 +2k 2 -α+1 ((q -1) 2 -(q -e)) -2q k 1 +k 2 +2

+ 2(q -1)(q -e)q 2k 2 -α + 2(q -1)q k 1 +1 + 2(q -e). (29)

In order to have terms noninterfering in (29), we impose the following inequalities on the parameters,

2 ≤ k 1 + 1, (30) 2 ≤ (2k 2 -α) -(k 1 + 1), (31) 3 ≤ (k 1 + k 2 + 2) -(2k 2 -α) = k 1 -k 2 + 2 + α, (32) 1 ≤ (k 1 + 2k 2 -α + 1) -(k 1 + k 2 + 2) = k 2 -α -1. ( 33
)
Then we get s(w 2 ) = (k 2 -α -1)(q -1) + g(q, e) where g(q, e) = s q (2(q -e)) + s q (2(q -1)) + s q (2(q -1)(q -e))

+ s q (2(q -1) 2 -(q -e) -1) -1. (34)

Summing up, we have s q (u 2 ) + s q (2uv) + s q (v 2 ) = (q -1)(n 1 + 1) + f (q, e) + (q -1)(n 2 + 1) + (k 1 -1)(q -1) + 2 + (k 2 -α -1)(q -1) + g(q, e) = (q -1)(2k 1 + 3k 2 -2α) + f (q, e) + g(q, e) + 2.

Combining with (25) and (28) we therefore have (35) (q -1)(2k 1 + 3k 2 -2α) + f (q, e) + g(q, e) + 2 = (q -1)(2k 1 + 3k 2 -α) + e and α(q -1) = f (q, e) + g(q, e) -e + 2.

Rule (4) applied to (23) and (34) shows that the right hand side is indeed divisible by q -1 since e 2 -e ≡ 0 mod (q -1) by assumption. Furthermore, we have by a crude estimation (using also [START_REF] Lindström | On the binary digits of a power[END_REF]) that (36) 0 ≤ α ≤ 15.

  s for s of the form 3k with k ≥ 27. Summing up, we have infinite families of n with s(n 2 ) = s(n) = s for all s ≥ 22, respectively, s ∈ {12, 16, 18, 19, 20}. For s ∈ {13, 17, 21}, we take (N ) 2 = u0 R v with s = 13 : u = 10111, v = 10110111111 s = 17 : u = 111011111, v = 10110111111 s = 21 : u = 11110111111, v = 111101111111. This completes the proof of Theorem 1.4.

Table 1 .

 1 Odd n such that s 2

	7

Table 2 .

 2 Odd n such that s 2

	cont)

Table 3

 3 Let u = 47 = 101111. Given that s 2 (uv) ≥ 2 we have that s 2 (v) = 3 and s 2 (v 2 ) ≤ 2. There are no solutions by Table3for this, a contradiction.

	is v = 23 = 10111, but s 2 (uv) = 3, a contradiction.
	(2)

Table 3

 3

. s 2 (u) ≤ 8, s 2 (u 2 ) < s 2 (u) and s 2 (u 2 ) ≤ 6.

K.G. Hare was partially supported by NSERC. Computational support provided by CFI/OIT grant. Th. Stoll was partially supported by an APART grant of the Austrian Academy of Sciences.

Suppose k 2 ≥ 17. Then (30) and (33) are satisfied. Rewriting (31) and (32) gives

Note that k 1 ≥ k 2 +2 is more restrictive than the first inequality in (37).

On the other hand, since k 2 ≥ 2, the interval given for k 1 in (37) has at least (2 • 17 -α -1) -(1 + 17 -α) + 1 = 16 terms. Therefore, 2k 1 + 3k 2 hits all integers ≥ 2(1 + (k 2 + 1) -α) + 3(k 2 + 1) for k 2 ≥ 17. Thus, we find from (35) that all values (q -1)(2k

= 94(q -1) can be achieved. This completes the proof of Theorem 1.5.


Giancarlo Luxardo
email: giancarlo.luxardo@msha.fr

Françoise Rollan
email: francoise.rollan@msha.fr

Visualizing and monitoring emergent border issues in Central Asia

Twenty years after their independence, the five countries of Central Asia face a number of issues, which can be observed at their borders, inherited from the Soviet era. The borders demarcating one from another have been enforced as a result of the formation of new national identities. In contrast, more (official or smuggled) exchanges are taking place across the borders of the former USSR. Internet-based media specialized in Central Asia regularly report on events, conflicts and exchanges occurring in the area. They provide a considerable body of information in the form of press releases, which can help the researcher to understand how these events are triggered or interrelated. However, the amount of text rapidly becomes excessive for an individual researcher. Our approach is to assemble these reports in a text corpus and process them with text mining techniques, allowing both information extraction and text categorization. Our text corpus is built with reports (covering a period of 11 years) issued by the Institute for War and Peace Reporting (http://iwpr.net), which produces homogeneous and regular information based on reliable and neutral journalism sourcing. With the release dates of the reports it is possible to work on time series and if the corpus is enhanced with the ability to handle easy updates it is possible to monitor current events.

Introduction

After the collapse of the USSR in 1991, five new States have been established in Central Asia: Kazakhstan, Uzbekistan, Turkmenistan, Kyrgyzstan and Tajikistan. The borders dividing the new republics are the legacy of the Soviet era1 . However, the function of these borders has dramatically changed since the attainment of these countries to independence. While under the Soviet regime, they had limited significance beyond administrative matters, the reality of these borders has gained importance in the definition and control of a new territoriality, which could influence both the formation of new national identities and the organization of the emergent economies.

On the other hand, this area also represented a frontier for the USSR demarcating its territory from several Asian states (China, Afghanistan, and Iran) and these borders were on the contrary particularly hermetic. In the context of the globalization of the economy which followed the end of the USSR and as a result of the need for the new Central Asian states to find new partnerships in alternative to Russia, the exchanges observed at these borders have inevitably increased.

In other parts of the world, changes in local economies and the adaptation to globalization processes favoured the development of regional integration. However in Central Asia, as long as a number of issues questioning the stability of the existing regimes and the sovereignty of states are not solved, it is difficult to envision cooperation between states at regional level. Therefore, the new Central Asian republics are bound to two opposed trends: establishing new borders with their neighbours and allowing more exchanges in the framework of globalization.

How the new borders have reorganised the Central Asian space?2 These new borders are making life very difficult for people who want to exchange goods or who need to migrate to feed their family. How do people manage to bypass the border where this is possible? How are they able, despite all this, to keep in touch with family members on the other side of the line? How do they feel about these borders, arbitrarily drawn? How do ethnic lines interfere with the borders? What are the local consequences of the new borders, the regional consequences of water mismanagement? How do the NGOs have gained strength and are able to destabilise the Governments? What is the impact of radical Islam attempt to construct a community rival to that of the nation-state that would suppress the borders and overthrow the secular governments, and install the Sharia Law in Central Asia? How the foreign religious missionaries are convincing local people to adopt another religion? What is the influence of the proximity of Afghanistan and the drug and weapon trafficking on these countries? Are these countries strong enough to control their borders in order to stop extremist groups and smuggling? Are they able to coordinate their border policies to prevent conflicts?3 It is the interaction of multiple factors: economic, political or cultural, which operate in this area, both locally and globally, that we propose to assess. To do so, we take into consideration a large amount of information, derived from news reports on events occurring in the area, that we attempt to process using both qualitative and quantitative techniques, in order to provide new representations.

Borders marking out the limits of state authority: a qualitative approach

Following the collapse of the USSR, an increase of interest and studies about Central Asian States and their borders can be noticed. Besides the books4 , several Web sites are giving information on borders in Central Asia. 5 Our text corpus is made up of articles published by one of these Internet-based media services: the Institute for War and Peace Reporting (IWPR)6 . It has archives dating back to 2000 and regularly reports on political and social events related to the Central Asian Republics (several times a month), using also local surveys. Only articles related to border issues have been extracted. The corpus is comprised of 827 articles, collected from 2000 to the end of 2010. It has been completed by field surveys carried out in the Fergana region in Kyrgyzstan and Uzbekistan, in Khorezm and Karakalpakstan, in Sharisabz, in Tashkent area in Uzbekistan, in Bishkek, Talas and Naryn in Kyrgyzstan, in Almaty region and in Astana in Kazakhstan, and in Penjikent area in Tajikistan7 . Since 1991, the year of their independence, the new Central Asian countries have been supervising the definition of their borders. The delimitation of borders is the subject of tough negotiations between States and can last several years. The process is still going on. A major problem comes from the fact that several maps have been used to settle the borders during the Soviet period: one was drawn in 1924-1927 and the other one in 1955.

The function of borders

Borders are places of contact, exchange and confrontation. The establishment of borders in Central Asia produces a number of unprecedented challenges in a world where the tendency is for frontiers to be abolished. They are defining a new territoriality, in line with the newly created Nation-States and their dominant ethnic group, which coincides with the new citizenship of the inhabitants. But what is more important for people, better than kinship, is the place, the territory where they live, because they are bounded to space by memory. 8 What is currently happening on the ground represents a step backwards in time: a new "iron curtain" is breaking up an area which has never been divided before throughout its long history. Each country is gradually erecting boundaries with custom offices, border guards, fences of barbed wire or mining its border.

During the Soviet period, the frontiers were virtual ones, with no reality except on the map. Peoples living in these regions had never experienced a frontier. This was a totally unknown concept for them. People moved on a regular basis from one State to another, with no need for formalities since each Soviet citizen automatically received a passport which was also referring to the nationality (ethnic group), and thanks to it, could move around freely. In the 19 th century and at the beginning of the 20 th , the vast territory of Central Asia was called Turkestan, and everyone moved around freely. There was indeed a frontier with the Chinese Empire and with the area of British influence to the south, but no one crossed these borders, apart from a few nomads who were not recognised as citizens by any of the States.

Today the populations of the five Republics are beginning to learn what a border is. Families have been brutally split up by a line that is impassable or almost, a line that is closing in more tightly day by day. A visa is compulsory for anyone who wants to cross this line except for people living in the rayons bordering the frontier. Even though no visa is needed in this instance, a fee is levied for the crossing ($7), and the duration of these visits is limited. But in any case, a passport is required. Very close-knit families, who used to visit one another every week, can now do so only on special occasions.

Security and financial reasons may oblige the State to close its borders. Regularly, Kazakhstan, Kyrgyzstan and Uzbekistan close their borders either because some ethnic violence happened in the neighbouring country or to increase taxes on the imported goods by shuttle traders from Tashkent or from Bishkek. There is a stalemate with Turkmenistan as they have put up a barbed wire fence, particularly in Khorezm, in the Uzbekistan border region which historically stretched along both sides the Amudarya river.

For ordinary people, it is always possible to cross the border illegally, with a small bribe. Contraband food products, textiles and petrol are common currency in Kyrgyzstan and Uzbekistan. In the Fergana, a woman can bring in as much as 500 litres a day across the fields!)9 . Smuggling of drugs and weapons has complicity at the highest level10 . Lorries, carrying hundreds of tons of scrap metal, stolen in Uzbekistan and Kyrgyzstan, cross "legally", every day the Kyrgyz-Chinese border.

Fluctuating borders in post-Soviet Central Asia

Gerald Blake points out that: "The states of the former Soviet Union declared in December 1991 that they would respect the boundaries they have inherited, but a number of boundary and territorial disputes have nevertheless emerged." 11 The delimitation of the borders is currently being carried out, but as it is not completed, the border can be considered as mobile. Contesting and claiming space at the edges of the Nation States is what is being done regularly by the three countries (Uzbekistan, Tajikistan and Kyrgyzstan), which share the land of the Fergana Valley. That area is a sensitive sector as it is the most densely populated region, the richest in agricultural terms for Uzbekistan, Kyrgyzstan and Tajikistan, and it is also rich in energy and mineral resources (oil, water, gold). None of the three countries recognises the established border since two maps are used 12 . For example, Uzbekistan on its southern border, in order to protect itself against Islamic guerrillas incursions, has planted mines on its border, and has taken the opportunity to move the border in the mountain. Tajikistan and Kyrgyzstan have used the pretext of a guerrilla attack, and have moved some border posts in order to gain some space at the expense of the neighbouring country. One of these can decide unilaterally that a local river belongs to it and not to one it uses to be. A dam supposedly built by the Uzbeks has been taken with its lake to Kyrgyzstan in the Fergana valley and of course reduced the Kyrgyz territory.

Facing threats to state authority: information without borders

Regarding the borders, N. Polat has identified three kinds of problems: border issues (delimitation), ethno-border issues, transboundary water issues13 . These could be considered as physical/human border issues. However, another kind of borders is observed today. With the widespread use of the Internet, international communications are more difficult to control for the authorities. These "virtual borders" are easily overcome by international news agencies or human rights NGOs, while fundamentalist ideologies are dispatched by zealous militants. All this disturbs the authoritarian regimes in place since their independence.

Information, now without borders, is of great concern for these non-democratic governments: with Internet, the whole World is able to learn about the violations of Human Rights. It worries these Central Asian countries. Because of their inclusion in the globalisation, they are dealing economically, with Western countries. They need to export their natural resources on the global market which implies to have good relations with the other countries, especially with the richest ones which are also democratic and fight to impose democracy everywhere. It is difficult to close hermetically the information pipes, like internet, phone and satellite phone. After Independence, a lot of NGOs have entered these countries and they are now operating officially or not, helping the women to get their independence and more generally they introduce people to democracy and fight with the journalists for a free press, with the lawyers for an independent justice.

Internet and its powerful input-output mean of information worry the Central Asian regimes which started to fear the spread of the Arab Spring Revolt and to prevent it, are closing partially Internet access to their citizen. The media are also under high scrutiny and journalists who do not share the ideas of the President, are very often jailed. Since the independence, the opening of the borders has been a chance for the NGOs those fighting for democracy and human rights as well as those introducing religious ideas to enter these countries. Ideas do not have boundaries, they overpass the physical borders.

Other threats: religious movements, foreign to those regularly established in the country

-Muslim missionaries (from Saudi Arabia, Egypt, Pakistan, etc.), carrying extremist views, have been able to enter Central Asian countries after the Independence and they are trying to compete with the official Islam controlled and ruled by the State. In reaction to the collapse of the Soviet state and its communist ideology, women and men have turned increasingly to Islam as an easily accessible, socially approved route for self-identification. The state, however, has mishandled religious policy, and its approved clergy have been unable to meet the demand for religious instruction.

Lack of basic services, like healthcare, electricity and roads, erodes allegiance to the state and fuels public discontent. The vacuum is easily filled by militants or religious extremists whose messages find a ready reception among desperate populations. Economic hardship is driving Central Asian youngster into the ranks of militant Islamic forces. 14 The proximity of Afghanistan torn by a civil war is said to influence the spread of radical Islam through the Taliban, al Qaeda, calling for global Jihad or the Islamist Movement of Uzbekistan. Wahhabi propaganda or other movements such as Hizb ut-Tahrir, Salafis, act underground. All these movements laud radical Islam ideas and as a goal, want to establish an Islamic state. Drug trafficking with Afghanistan is used to fund their actions, propaganda and jihad. Trading arms for Taliban and Al Qaeda in exchange of heroin is the work of organized crime networks across Central Asia. The last clashes in southern Kyrgyzstan (Osh, 2010) might not be strangers to these criminal organizations, the "third forces"? Although, after the interethnic violence in Osh, its mosques were seen as a symbol of unity, they are now under greater scrutiny as ties between Islam and extremism emerge. 15 Extremist groups worry very much the governments of the five countries which are trying to fight them. But strong repression against the Islamist movements gives rise in number of supporters.

-Christian missionaries and others16 , as well, mostly from American protestant obedience. Mormons, Church of Jesus Christ of Latter-Day Saints, Baptists, Seventh Day Adventists, Jehovah Witnesses, Lutherans have been able to settle in these countries17 . Until the Independence, Orthodox Christian and Muslim clergy have coexisted equably, with neither trying to poach the other congregation. But now, they are deeply suspicious of these foreign groups, accusing them of offering aid in return for conversion. 18 They are trying to convert poor Muslims, giving them food. People are so desperate that in some cases it works, which brings threat in families, some members being becoming Christians and others remaining Muslims. The foreign-funded groups are able to offer their parishioners more than the longerestablished religions. Depending on the Church, the benefits may include free English and computer classes, foreign scholarships, business loans, or even flour and imported food. "Divisions within the family, which are inevitable if individual members adhere to different beliefs, lead to schisms in society, in the state itself, as a whole."19

Globalised economy and politics: foreign military bases

At a global level, different events occur as a result of the activities of the new states in the globalized economy: pipelines and new transnational roads to transport natural resources and goods, migrations of Central Asian people to Russia and Europe looking for a better standard of living and for disregarding of human rights. The foreign military bases and foreign military landing facilities make up provisional foreign territories in the Central Asian countries. They are related to the Operation Enduring Freedom led by the US and the UK and other NATO and non-NATO countries, in Afghanistan after 9/11. They are granted to the coalition forces. They constitute another kind of mobile borders inside one Central Asian country because these facilities can be suppressed anytime by the host country. It happened in Uzbekistan when President Karimov disliked the political position of the US, following Andijan events. Termez base and other landing military facilities for the US were cancelled from Uzbekistan. After Andijan, Russia was again welcomed in Uzbekistan since it did not criticize President Karimov protestor slaughtering and did not say anything about the non-compliance with human-rights.

Establishing a military base implies establishing new borders around the base, which necessitate a very strict procedure to enter the base. Security measures are even tougher than at a country border and bribes are not possible because if a local soldier can be corrupted at the border, a foreign soldier (American or Russian) is much more likely to be incorruptible.

Categorization of border issues: a quantitative approach

The text corpus is comprised of 827 articles with a total number of approximately 840,000 word occurrences, among which 30,000 are distinct words. This represents about 1 400 pages of an MS-Word document. A number of text analysis software tools have been experimented for this project. The results described in the following have been produced with DTM-Vic 20 , a software freely downloadable on the Web.

Defining the variables

The text corpus being segmented by article, three types of variables have been assigned to each article: -date (month -year), the publication date which may allow to study time series, (11 modalities) -category, a "hand-coded" variable identifying the main topic of the article according to a simple coding scheme based on 12 modalities, -border, a "self-assigned" variable identifying the most relevant border (i.e. the two countries) mentioned in the article. For the encoding of the category variable, a specific content analysis software has been considered (most of the available tools are based on dictionaries with a hierarchy of categories). However, this approach was not pursued because the first tests showed that the related procedures were more time-consuming than the plain browsing of the text.

The border variable is provided by the execution of a number of scripts which also perform various pre-processing tasks on the text. These scripts (written in the Groovy language) recognize the most frequent occurrences of locations and infer the border mainly concerned by the article. This border may refer to two of the five Central Asian countries or one of them and another country among Afghanistan, China, Iran or Russia (it does not necessarily match a "physical" border). It includes 15 modalities. These three variables allow to partition the corpus according to respective modalities and to complement statistical calculations run on the text (factorial analyses, clustering).

For this corpus, the 12 categories identified and related to border issues in Central Asia are the following: -border (border delimitation and disputes), -defense (security, terrorism, infiltrations), -economy (trade, shuttle trade, transport, roads, tourism), -energy (oil, gas, pipelines, electricity), -ethnic issues (ethnic conflicts, discrimination, language policy), -foreign military bases (including landing facilities for war planes), -ideology (religious or political movements, NGOs), -international relations (with influence), -migrations (international migrations including refugees and the associated problems), -police (harassment, human rights, freedom of press, of religion, independent justice), -smuggling (drugs, weapons, scrap metal, cotton, etc), -water (Amu Daria, Syr Daria, Illi, Irtysh, Balkash Lake, Aral Sea, dam, water pollution).

Choosing the statistical processing: the ascendant hierarchical classification

Several statistical processings of the texts have been tested. The best result is obtained from a clustering of articles using an ascendant hierarchical classification -reciprocal neighbours method, on the factors of a multiple correspondence analysis on the variables and on the texts. After several iterations, the description of the classes allows a categorization in 12 classes, based on the frequency of words. According to the clustering method, the variance interclass should be maximized and the variance intraclass minimized, so that the classes should be as homogeneous as possible and the classes as different as possible. The graphic output of the clustering represents a dendrogram. Then, the interpretation is checked by returning to the text.

What is expected in the definition of classes is not to find back the initial categories but a more precise definition with more complex variables. Each class should be identified by a series of modalities of the variables 'category', 'year' and 'border'.

The best clustering, described in the following, produces 12 classes (Fig. 1 andAppendix). Each text is assigned to a class and each class is illustrated by the 20 most characteristic words21 , which helps in defining the meaning of the classes. The dendrogram can be cut at different levels: going from the bottom to the top, this allows to synthesize and group the different issues. At the top of the dendrogram, only two groups are observed. The description of the classes could lead to the following interpretation.

Analysing the dendrogram in 12 classes

Starting from the bottom of the tree, the 12 classes are identified in the following way:

-Class 1 represents a quite homogenous class. It is devoted to oil and gas export routes to Europe and the policy followed by President Niazov to diversify these routes (through Iran, Afghanistan and/or through Russia) to the global market. However Turkmenistan poses a problem to Western partners. They worry because Turkmenbashi does not comply with Human Rights. Depriving Niazov from buying its large oil and gas production constitutes a lever of pressure, since Western countries are the strongest Human Rights defenders.

-Class 2 is totally oriented towards Kazakhstan and its relations with Russia, Turkmenistan and OSCE that Nazarbaiev has finally chaired in 2010. Because of human rights concerns, the decision has been delayed. Kazakhstan has problems with the Russian minority who is calling for autonomy. It is to preserve the country territorial integrity that President Nazarbaiev moved the capital from Almaty to the northern city of Astana. Kazakhstan is also engaged in the globalization process with its rich oil production and other mineral deposits.

-Class 3 is well identified and refers to the Central Asian migrants, especially the Tajik citizens, going mostly to Russia to find a job. The economic situation is so desperate that hundreds of thousands of young men are leaving the country, in hope to find work in Russia, in order to feed their family. Although many are illegal workers, they send a lot of money to Tajikistan, which helps the national economy to survive. Illegal workers are vulnerable and face discrimination and violence in Moscow.

-Class 4 is related to radical Islam with IMU 22 , the Talebans and the war in Afghanistan in which the US are engaged. Uzbekistan is also on the same side as the Americans since they have to fight the Islamic Movement of Uzbekistan led by Takhir Yuldash. Tashkent has provided military bases to the Americans. International relations are woven between Afghanistan and several countries that fear the Talebans. This class represents the globalization of the war in Afghanistan in which Central Asian countries are also engaged because they feel threatened.

-Class 5 is only linked to the foreign military bases related to the fight in Afghanistan, installed in several Central Asian countries (in Uzbekistan and Kyrgyzstan for the Americans and in Tajikistan and Kyrgyzstan for the Russians). Some landing and refueling facilities are also given to the coalition forces (in Uzbekistan and in Kazakhstan) -Class 6 is associated to economy and especially trade with China. There is an unfair competition between the local traders and the Chinese traders who are invading and breaking the prices of the local markets; It is a problem for Kyrgyzstan which is bordering China and for Uzbekistan which has access to Chinese goods through the Kyrgyz markets. This is a regional problem but related to the globalization of the economy.

-Class 7 aggregates social unrest and ethnic violence between Kyrgyz and Uzbeks in Osh and Jalalabad and which forced President Bakiev to resign. It appears that the rights of the South are not respected in the government. Some radical Islamist organizations like Hizb ut-Tahrir, are acting underground and preparing the society to move to an Islamic state. This class shows the ethnic problems with their political consequences.

-Class 8 gathers police problems related to virtual borders. The growth of the Islamic radical group Hizb ut-Tahrir is worrying the Central Asian governments that are adopting tougher approach (Kazakhstan). Women are among the best followers of these groups. Internet constitutes a serious threat to these authoritarian regimes and they try to limit the access (Kazakhstan, Uzbekistan) or to forbid it (Turkmenistan).

-Class 9 is associated with regional water problems and energy supply. Water supply problems in the Aral region, lack of water for irrigating the cotton agriculture, for fishing industry and disputes between Kyrgyzstan, Tajikistan and Uzbekistan are serious. The power plant projects in Kyrgyzstan and Tajikistan will reduce water available for agriculture. Kazakhstan and Russia are trying in vain to mediate the situation. The situation seems difficult because the five states lack a common vision on how to harmonise their differing interests since resources are unevenly distributed. Tajikistan and Kyrgyzstan, upstream countries, possess 80% of the water resources. Uzbekistan, Kazakhstan and Turkmenistan, the downstream countries, have gas and oil resources and no water for their agricultural needs. Uzbekistan wants to sell gas to the upstream countries but does not want to pay for water. Any new dam project makes the Uzbek government furious. An example of conflict involving multiple interwoven ramifications of events at work on the borders of Central Asia follows. The construction of a hydropower plant in Tajikistan could trigger an international problem, with Uzbekistan preventing Iran from delivering equipment for the plant, which would reduce the water available for Uzbek agriculture. Iran has replicated by threatening to stop Uzbek trains exporting goods through Iran. A local and regional issue could escalate into an international one.

-Class 10 assembles local border problems and their related tensions. There are about land belonging to Kyrgyz, Uzbek, Tajik and Kazakh. Incidents are frequent with the border guards and death tolls happen. In some areas (Fergana) the borders as a legacy of the Soviet Union are making the situation impossible to solve. Batken region with its enclaves is one of these.

-Class 11 brings together smuggling of drug(s), weapons associated to Afghanistan. Use of heroin has brought HIV. Police and custom officers are corrupted, which facilitates smuggling of all kind of goods. Drug is introduced in Tajikistan from Afghanistan by smugglers who cross on foot the border in very remote and difficult places where not even a mule could pass. Drug is exchanged against Kalashnikov at a very low price at the border23 . This shadow economy brings a lot of insecurity at the borders. Drug addiction and poverty is responsible for extension of HIV. Police is participating in drug trafficking and provide protection for the drug trade not only in Tajikistan but even in Kazakhstan. Metal smuggling, from Kyrgyzstan to China, represents also a great loss for the economy.

-Class 12 is associated with radical Islam guerrillas. Militants are engaged in the IMU movement and they are also fighting with the Taleban, attacking the security forces of Uzbekistan and Kyrgyzstan. The greatest threat is in Batken region (Kyrgyzstan) and Andijan (Uzbekistan). The instability in Afghanistan and the loose state in Tajikistan facilitate the incursions in the neighbouring countries. It seems that conditions are assembled to extension of conflict and put Central Asia at risk.

Synthesizing the ascendant hierarchical classification

-If the tree is cut in eight classes: the two first classes are united by the international relations between Central Asia, Russia, Iran, Afghanistan and Europe, because of export routes for oil and gas from Turkmenistan and Kazakhstan. Both have ethnic problems with their Russian minority that cannot get double citizenship. Both are engaged in the globalization process although the human rights violations could be a potential bottleneck for Western countries, but not for Russia nor for China. The third class is self-identified and remains stable (International labour migrations). The fourth and fifth form one class related to international relations and interventions in Afghanistan; the sixth is stable (border economy and China implication). The seventh and eighth classes regroup in one and could represent human and virtual borders, with ethnic violence and political consequences and virtual borders as defined with police problems against the NGOs. The ninth and tenth add up to represent the physical border issues (regional water problems and border limits). The eleventh remains that of smuggling and the twelfth the guerrilla infiltrations due to the proximity of Afghanistan.

-With six classes, the first four groups remain unchanged. The virtual and human borders and the physical borders issues get aggregated in one group which could be called: virtual and physical border issues. The original last two classes regroup and represent illegal border crossing. -With four classes, it is easier to differentiate global and regional/local problems. The globalization appears with oil and gas and international labour migrations, and with the border economy and economic relations with China are still visible because this group is well identified and homogenous since it gets aggregated at a very low level. The other issues represent regional problems.

-The highest level presents only two classes: the global issues (the first five classes) and the local and regional issues which include the seven following classes. What can be seen is that, in all the issues, several external actors to the Post-Soviet countries are very active: Afghanistan, Russia, the US and China. To a lesser degree, Iran, Turkey and Europe are trying to play a role. The external actors do not want to miss the fossil energy resources. The Americans are pushing in favour of a route through Afghanistan and then Pakistan instead of the one through Iran, to reach the global market. China would prefer to double its route through Central Asia and is ready to increase the price.

Within the second group, some local problems could degenerate into regional and may be into global ones, such as water issues and drug and weapon smuggling. Europe and the US are worrying very much about the porous borders of Tajikistan and are asking to International organizations to help the country learning how to control strictly its borders.

The quantitative approach allowed to classify the border issues in Central Asia, to highlight the inter-relationships between the different events occurring at the borders and to organise the problems into global and local/regional issues which was not apparent through a sequential reading.

Conclusion

Inter-ethnic border problems could be considered as the legacy of the Soviet Empire. Most of ethnic conflicts between populations living on both sides of a border in Central Asia are due to a border drawn fairly arbitrarily between the Soviet republics and now sovereign states. This is the case for Kyrgyzstan, Uzbekistan and Tajikistan. The Fergana valley divided between three sovereign states (Uzbekistan, Tajikistan and Kyrgyzstan) is the most sensible area to this problem. As a result, people belonging to the same ethnic population are attached to different countries. In the country where they constitute a minority their rights are not always recognised or enforced. This situation leads to ethnic violence (Andijan in 2009, Osh, Jelal Abad in 2010) which could have serious consequences for the stability of the region. With the resurgence of local ethnic identities, the situation has become very sensitive.

The five states really do need to cooperate, if only to manage their water resources, but these border problems are so serious that each one manages them in its own way, preferably by inconveniencing its neighbour. Tensions are steadily increasing between them. Behind the frontiers, the problem is a political one. Uzbekistan, the most populated country and economically the most advanced, would like to be the leader of the region. Its rapprochement with the United States proves its will to detach itself definitively from Moscow. Kazakhstan, the largest in area, and very rich in energy and mineral resources, has chosen the Russian route because there is a problem with an important Russian minority in the north on its border with Russia, who is simply asking to secede, hence the transfer of the capital to Astana. But Kazakhstan tries to diversify its alliances. It disdains neither China nor the United States nor Europe nor Turkey. President Nazarbaiev, who chaired OSCE in 2010, is doing his best to organize cooperation for the management of water resources. Kyrgyzstan, which contains the sources of the Syr Daria, is not short of water but nor does it have anything else; after September 11, the Kyrgyz agreed to the presence of an American base and more recently, to a Russian one. However, the Kyrgyz language has recently become compulsory for all administrative purposes, which is an obstacle to inter-ethnic understanding. Turkmenistan, a rich country because of oil and gas resources, is isolating itself and has cut off all links, including those with Russian residents, who are now obliged to leave the country. The main finger of blame is pointed at Tajikistan, the poorest State, because it allows drug traffickers to pass through and is believed to be harbouring Islamic terrorists. One question should be raised: in such a globalised world, do the poorest Central Asian countries (Tajikistan and Kyrgyzstan) have the means of controlling their borders? International Organisations are trying to organise the training of border guards, but what is needed is an integrated border control. 24

20

  Data and Text Mining, Visualization, Inference, Classification; http://www.dtmvic.com

Fig. 1 -

 1 Fig.1-Ascendant hierarchical classification diagram (for the original dendrogram see appendix)

Haugen A.2003, p.149-210. 1

Gavrilis G., 2010, p.93-104.

Gavrilis G., 2010, p.118-129.

See Bibliography.

Examples: http://www.eurasianet.org; http://iwpr.net; http://www.irinnews.org; http://www.dur.ac.uk/ibru/; http://centralasiaonline.com/cocoon/caii/xhtml/en_GB/homepage/; http://enews.fergananews.com/; http://www.rferl.org; http://crisisgroup.org; http://www.cacianalyst.org; http://www.centralasianews.net;

IWPR: an NGO in London and New York, which gives voice to people at the frontlines of conflict, crisis and change. IWPR forges the skills and capacity of local journalism, strengthens local media institutions and engages with civil society and governments to ensure that information achieves impact.

Field surveys totalizing several months between 1997 and 2011.

[START_REF] Wijhe Alex Van | Theorizing territory[END_REF], http://criticalgeography.wordpress.com/2010/12/01/theorizing-territory/,(accessed Jul. 20, 2011)

IWPR, RCA Issue 38, Jan 2001 http://iwpr.net/report-news/petrol-smuggling-rings-lure-kyrgyz-women

Gavrilis G., 2010, p.144-151.

Blake G., 2000, In: M. Pratt and J.A. Brown, Borderlands under Stress, p.4

One from 1924One from -1927 and the other one from 1955.

N. Polat, 2002, Boundary issues in Central Asia.

Rashid A., 2003, Jihad. The Rise of Militant Islam in Central Asia.

January 23, 2011, http://www.rferl.org/content/kyrgyzstan_mosques_under_scrutiny/2284606.htm

Like Hare Krishna, very active in Kazakhstan.

There are currently some 300 Christian groups in Kyrgyzstan. IWPR, RCA Issue 531, 13 Feb 2008, http://iwpr.net/report-news/tighter-regulation-worries-kyrgyz-faith-groups

Around 85 non-Islamic religious organizations are registered in Tajikistan, predominantly minority Christian groups. IWPR, RCA Issue 502, 23 Jul 2007, http://iwpr.net/report-news/tajikistan-bill-religious-practice-raisesconcern (last access July 24th, 2011)

 19 IWPR, RCA Issue 239,

 Sep 2003, http://iwpr.net/report-news/missionaries-offer-faith-and-food-kyrgyz (last access July 26th, 2011)

The number of words is a parameter, determined by the researcher.

Islamic Movement of Uzbekistan

http://iwpr.net/report-news/turning-afghan-heroin-kalashnikovs, ARR Issue295, 9 Jul 08, 1 kg of heroin is exchanged for 10 Kalakovs (AK-74) or 15 [old mode]l Kalashnikovs

Gavrilis G., 2010, p.162-165.