Moskva, Moscow, Russian Federation
Moskva, Moscow, Russian Federation
GRNTI 50.43 Системы автоматического управления, регулирования и контроля
This work is about the generalization of sum-product problem. The general principle of it was formulated in the Erdos-Szemeredi’s hypothesis. Instead of the Minkowski sum in this hypothesis, the set of values f(x,y) of a homogeneous polynomial f lin two variables, where x and y belong to subgroup G of is considered. The lower bound on the cardinality of such set is obtained. This topic has an applied value in the theory of information and dynamics in calculating the probabilities of events, as well as in various methods of encoding and decoding information.
sum-product problem, residue field, multiplicative group, subgroup
Introduction
This work touches upon questions of arithmetic combinatorics, which studies simultaneously additive and multiplicative operations on sets. One of the most fundamental questions is the problem of sum-product subsets. The detailed description of it can be found in the paper [1]. The problem below has numerous applications in several branches of mathematics, such as cryptography for codes and dynamical systems. The results associated with the problem of sum-product type in a field of positive characteristic enable us to solve the problem of estimating trigonometrical sums over subgroups, which is particularly important for number theory. These estimates make it possible to describe the distribution of the elements of a multiplicative subgroup in a field of positive characteristic.
Let A be a finite non-empty set of elements of a ring K (for example, a finite set of integers). Consider the sum and product of A with itself:
(1)
(2)
Obviously, the cardinality of both these sets is at least and in general the expectation is that it to be close to . However, if is closed under addition and multiplication ( is closed to a
subring), then the cardinality of both sets and can be comparable to . For the ring
of integers, the Erdos - Szemeredi’s hypothesis says that there exists a positive number for which the following inequality holds:
(3)
for any finite subset of a ring. The inequality means that there exists a positive number such that . This is the sum-product phenomenon: if the finite set is not close to a real ring, then the sum or the product must be considerably larger than and close to .
This phenomenon was not proved, however, there is Erdos - Szemeredi’s theorem for finite set of integers which states:
,
where – positive constant.
Estimates for the constant were constantly improved. If the set , then best result was proved by Solymosi based on the Szemeredi-Trotter theorem:
. (4)
Remark: Consider the analogous problem of estimating the cardinality of the set In the construction of this problem both additive and multiplicative operations are applied. It is known that .
In 1999 Tom Wolf (see [1]) raised the idea of looking for the phenomenon of sum-product type in finite fields of prime order (such fields do not have non-trivial subrings). In particular, the inequality (3) holds if and does not coincide with the entire field , in the sense that for some (it is reasonable that should depend on ), which was subsequently resolved positively. Now the corresponding result is known as the theorem on estimates of sums of products for (later he had new proofs and refinements).
It follows from the sum-product phenomenon that if the set of medium size has a multiplicative structure (for example, is a geometric progression or multiplicative subgroup), then it cannot have an additive structure: the sum is more larger than the original set . Further, it is concluded that sets with multiplicative structure are uniformly distributed in the additive sense.
There are some modern results in the sum-product problem:
Theorem (Konyagin-Shkredov, Rudnev-Steven-Shkredov, 2016 - 2017)
Let . Then
,
where is infinite, is an absolute constant.
Theorem (Roche-Newton-Rudnev-Shkredov, 2016, Askoy-Yazici-Murphy-Rudnev-Shkredov, 2017)
Let , . Then
.
Additive shifts of multiplicative subgroups
This problem is widely applicable in algebra, for example, in the study of additive shifts of multiplicative subgroups.
GarciaandJ. Volochin 1988 [7],using some algebraic ideas, provedthat for any multiplicative subgroup and any :
. (5)
D. Heath – Brown and S. Konyagin [4] simplified the proof of this fact and improved the constants in 2000 with the help of method of S. Stepanov [6], that is extremely popular in number theory. After that in 2012 I. Vyugin and I. Shkredov [3] generalize this fact for the number of additive shifts:
Let - multiplicative subgroup, – an integer, . Let - different non-zero residues and – an invariant set such as:
.
Then
This theorem leads to the statement about the maximum of the cardinality of the intersection of additive shifts of subgroup:
Let
.
Then
In other words,
.
If , where – some sequences of positive numbers and .
Also, in that work another additive characteristic of multiplicative subgroups is considered, namely, the cardinality of its sum and difference. The estimate (5) leads to
.
For any , for which . Indeed, considering the cardinality of union of group with some elements of group
then it equals to
from (5). If taking , where – some constant, then the previous inequality will look like:
The last part of the sum is linear, that can be omitted, so:
,
that means that
,
since
.
This result will be generalized for polynomials in Theorem 2(trivial bound).
D. Heath – Brown and S.Konyagin proved the inequality
for all subgroup , for which . Using the combinatorial idea, I. Vyugin and I. Shkredov made the previous inequality stronger:
for all subgroup , for which .
In this work the problem of the sum-product type for multiplicative subgroups is extended, and the lower bound of the number of solutions for the set where is a multiplicative subgroup, is obtained. The obtained estimate generalizes the earlier ones (see [1, 2]). These estimates are a corollary of author’s result if the linear polynomial is considered.
Preliminaries
Definition 1. Let us call the polynomial good if it is homogeneous with respect to , and is absolutely irreducible (it is irreducible over the algebraic closure of ).
Definition 2. For a prime number and a natural number , let us call a group – admitted if and .
Theorem 1 (I. Vyugin, S. Makarychev). For any natural number there exist constants such that for any prime number , for any – admitted group , for any good polynomial of degree , for any natural and numbers in different -cosets, there are at most
pairs for which for some . Later one of the constants in the last theorem was found exactly:
Main results
Let us begin with the supporting statement:
Lemma. Let be a homogeneous polynomial of degree such that the polynomial is irreducible over algebraic closure of . Then the polynomial , where is a constant in is irreducible over the closure of .
Proof. For any from there must be denoted by the root of the – th power from in the algebraic closure of .The polynomial is irreducible because if
then substituting into this equality and instead of and , then
i.e. is reducible, that contradicts to the assumption. So,
is irreducible. Multiplication by the constant α does not change irreducibility.
Theorem 2 (trivial bound). For any there exist such that for any prime number – admitted group and a good polynomial of degree :
.
Here is the set of all elements of that can be obtained by substituting all possible elements of as .
Proof. Consider the equation . There are two cases: and .
1) For any , the Theorem 1 can be applied (according to Lemma, is absolutely irreducible), taking (that has at most solutions for a constant depending only on the polynomial ).
2) If , then the number of pairs for which is at most .
a) If ( vanishes when is substituted), then there are no more than values of (for example, the leading coefficient of must vanishes, and its degree in is not greater than ). They give no more than pairs for which the vanishes.
b) If the polynomial does not vanish (the given is substituted), then it turns into a nonzero polynomial in of degree no greater than . Therefore, this polynomial has no more than roots. In total, this gives at most pairs for which the polynomial vanishes. Now it is needful to estimate the number of values of good on elements from the –admitted group G.
As (see Definition 2), then
.
As it was proved above, there are at most solutions
,
this means that there are smaller than one fiftieth of all possible pairs. Remaining at least pairs must somehow be distributed among other values of , but each of these values does not exceed pairs. Hence, the number of values cannot be less than
(5)
As (see the Theorem 1), then
.
The goal of this paper is to improve the lower bound of the number of solutions of the set .
Theorem 3 (non-trivial bound). For any there exist such that for any prime number – admitted group and a good polynomial of degree :
.
Proof. Suppose the contrary. Then there exists , for which Theorem 3 is not correct. Then for any constant there are the admitted group and the good polynomial such that
.
To obtain a contradiction, Theorem 1 must be applied. Thus, for it needs to be chosen some
satisfying the condition of Theorem 3. After this let us choose such that
.
Take any bad pair for the chosen . All possible values of that are not more
than can be arranged in the form of the Young tableau in such a way that each row contains values from one -coset, and in different rows - from different -cosets . Thus, each line of the resulting diagram has no more than elements. Let us estimate from above the number of pairs for which the value lies into one or another column.
If some column has elements, then it can be noted that . Therefore, since all the elements of the column lie in different - cosets, according to the Theorem 1, there exists at most pairs for which lies into this column. The number of pairs for which is at most (see the proof of Theorem 2).
Now it can be denoted the column lengths for and estimate the total number of pairs:
.
On the other hand, by the inequality on the power averages:
.
The sum of all is the total number of cells in the table, so it does not exceed , whence:
.
As (see Definition 2), it is a contradiction, and therefore, theorem is proved.
The constant
as was not found yet.
Conclusion
In this paper, the sum-product problem for multiplicative subgroups is expanded, and the lower bound for the number of solutions for the set is obtained. The received estimate generalizes the ones previously obtained (see [1,2]). These estimates are a consequence of the obtained result assuming that the polynomial is linear. The results that are considered in this paper, are intricately connected to another problems in additive combinatorics, namely, the additive energy of two sets and the structure of sumset problem, which allows to obtain the improved estimates for the cardinality of such sets.
1. Tao, T. Struktura i sluchajnost' - M: MCNMO, 2013. - 360 p.
2. Corvaja, P. Greatest common divisor of u-1, v-1 in positive and rationalpoints on curves over finite fields / P. Corvaja, U. Zannie // L. Eur. Math. Soc., 15, 1927- 1942, (2013). - Pp.345-356.
3. V'yugin, I.V. Ob additivnyh sdvigah mul'tiplikativnyh podgrupp / I.V. V'yugin, I.D. SHkredov // Matem. sb., 2012. - T. 203, № 6. - Pp. 81-100.
4. Heath-Brown, D. R. New bounds for Gauss sums derived from k-thpowers, and for Heilbronn’s exponential sum / Heath-Brown, D. R. S. Konyagin // Q. J. Math., 51: 2 (2000). - Pp. 221-235.
5. Konyagin, S. V. Ocenki dlya trigonometricheskih summ na podgruppy i dlya gaussovyh summ", IV internac. konf. Sovremennye problemy teorii chisel i ee prilozheniya, Aktual'nye problemy. CHast' 3 (Tula, 2001). - Izd: Mosk. un-ta. - 2002. - Pp. 86-114.
6. Stepanov, S. A. O chisle tochek giperellipticheskoj krivoj nad prostym konechnym polem / S. A. Stepanov // Izv. AN USSR. - 1969. - Pp. 1171-1181.
7. Garcia, A. Fermat curves over finite fields / A. Garcia, J. F. Voloch // Number Theory, 30: 3 (1988). - Pp. 345-356.
8. Katz, N. H. On additive doubling and energy / N. H. Katz, P. Koester. SIAM J. Discrete Math., 24:4 (2010). - Pp. 1684-1693.
9. Sanders, T. On a non-abelian Balog-Szemeredi-type lemma, arXiv: 0912.0306.
10. Sanders, T. Structure in sets with logarithmic doubling, arXiv: 1002.1552.
