Maximum subsets of $${{\mathbb {F}}}^n_q$$ F q n containing no right angles
- PDF / 262,161 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 153 Views
Maximum subsets of Fnq containing no right angles Gennian Ge1 · Chong Shangguan1,2 Received: 13 January 2018 / Accepted: 4 October 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract Recently, Croot, Lev and Pach (Ann Math 185:331–337, 2017) and Ellenberg and Gijswijt (Ann Math 185:339–443, 2017) developed a new polynomial method and used it to prove upper bounds for three-term arithmetic progression free sets in Zn4 and Fn3 , respectively. Their approach was later summarized by Tao and is now known as the slice rank method. In this paper, we apply this method to obtain a new upper bound on the cardinality of subsets of Fqn which contain no right angles. More precisely, let q be a fixed odd prime power and x · y be the standard inner product of two vectors x, y ∈ Fqn , and we prove that the maximum cardinality of a subset A ⊆ Fqn without three distinct elements x, y, z ∈ A satisfying (z − x) · (y − x) = 0 is at most n+q q−1 + 3. For sufficiently large n, our result significantly improves the previous upper bound of n+2 Bennett (Eur J Combin 70:155–163, 2018), who showed that |A| = O(q 3 ). Keywords Extremal combinatorics · The polynomial method · Right angles over the finite field Mathematics Subject Classification 05D05 · 15A03 · 15A69
Research supported by the National Natural Science Foundation of China under Grant Nos. 11431003, 61571310 and 11971325, Beijing Scholars Program, Beijing Hundreds of Leading Talents Training Project of Science and Technology and Beijing Municipal Natural Science Foundation.
B
Chong Shangguan [email protected] Gennian Ge [email protected]
1
School of Mathematical Sciences, Capital Normal University, Beijing 100048, China
2
School of Mathematical Sciences, Zhejiang University, Hangzhou 310027, China
123
Journal of Algebraic Combinatorics
1 Introduction The recent breakthrough results of Croot, Lev and Pach [5] and Ellenberg and Gijswijt [6] showed, respectively, that three-term arithmetic progression free sets in Zn4 and Fn3 are exponentially small. The main idea in their proofs was an application of a novel polynomial method, which was later summarized by Tao [17] as a principle which compares the slice ranks (see Sect. 2 below) of different multivariate functions. The problems investigated in [5,6] can be viewed as extremal problems defined over the finite fields which forbid the existence of certain configurations. In order to deal with this type of problems by the polynomial method, the essential idea is to characterize the property of having no such configurations by an equation between two carefully chosen functions. For example, let the forbidden configuration be the threeterm arithmetic progression, then a subset A ⊆ Fn3 contains no such configurations if and only if for three elements x, y, z ∈ A, x + y + z = 0n if and only if x = y = z. In [17], this observation is described as an equation between two F3 -valued functions defined on A × A × A: 1x+y+z=0n = 1x=y=z ,
(1)
where for any I (here I can be an equation, an event, etc.)
Data Loading...
