ID: 1705.06581

Products of Differences over Arbitrary Finite Fields

May 18, 2017

View on ArXiv
Brendan Murphy, Giorgis Petridis
Mathematics
Combinatorics
Number Theory

There exists an absolute constant $\delta > 0$ such that for all $q$ and all subsets $A \subseteq \mathbb{F}_q$ of the finite field with $q$ elements, if $|A| > q^{2/3 - \delta}$, then \[ |(A-A)(A-A)| = |\{ (a -b) (c-d) : a,b,c,d \in A\}| > \frac{q}{2}. \] Any $\delta < 1/13,542$ suffices for sufficiently large $q$. This improves the condition $|A| > q^{2/3}$, due to Bennett, Hart, Iosevich, Pakianathan, and Rudnev, that is typical for such questions. Our proof is based on a qualitatively optimal characterisation of sets $A,X \subseteq \mathbb{F}_q$ for which the number of solutions to the equation \[ (a_1-a_2) = x (a_3-a_4) \, , \; a_1,a_2, a_3, a_4 \in A, x \in X \] is nearly maximum. A key ingredient is determining exact algebraic structure of sets $A, X$ for which $|A + XA|$ is nearly minimum, which refines a result of Bourgain and Glibichuk using work of Gill, Helfgott, and Tao. We also prove a stronger statement for \[ (A-B)(C-D) = \{ (a -b) (c-d) : a \in A, b \in B, c \in C, d \in D\} \] when $A,B,C,D$ are sets in a prime field, generalising a result of Roche-Newton, Rudnev, Shkredov, and the authors.

Similar papers 1

Products of Differences in Prime Order Finite Fields

February 5, 2016

91% Match
Giorgis Petridis
Combinatorics

There exists an absolute constant $C$ with the following property. Let $A \subseteq \mathbb{F}_p$ be a set in the prime order finite field with $p$ elements. Suppose that $|A| > C p^{5/8}$. The set \[ (A \pm A)(A \pm A) = \{(a_1 \pm a_2)(a_3 \pm a_4) : a_1,a_2,a_3,a_4 \in A\} \] contains at least $p/2$ elements.

Find SimilarView on arXiv
Ilya D. Shkredov
Number Theory
Combinatorics

In our paper we study multiplicative properties of difference sets $A-A$ for large sets $A \subseteq \mathbb{Z}/q\mathbb{Z}$ in the case of composite $q$. We obtain a quantitative version of a result of A. Fish about the structure of the product sets $(A-A)(A-A)$. Also, we show that the multiplicative covering number of any difference set is always small.

Sum-product estimates over arbitrary finite fields

May 23, 2018

89% Match
Doowon Koh, Sujin Lee, ... , Shen Chun-Yen
Number Theory

In this paper we prove some results on sum-product estimates over arbitrary finite fields. More precisely, we show that for sufficiently small sets $A\subset \mathbb{F}_q$ we have \[|(A-A)^2+(A-A)^2|\gg |A|^{1+\frac{1}{21}}.\] This can be viewed as the Erd\H{o}s distinct distances problem for Cartesian product sets over arbitrary finite fields. We also prove that \[\max\{|A+A|, |A^2+A^2|\}\gg |A|^{1+\frac{1}{42}}, ~|A+A^2|\gg |A|^{1+\frac{1}{84}}.\]

Find SimilarView on arXiv

On growth of the set $A(A+1)$ in arbitrary finite fields

July 29, 2018

89% Match
Ali Mohammadi
Number Theory

Let $\mathbb{F}_q$ be a finite field of order $q$, where $q$ is a power of a prime. For a set $A \subset \mathbb{F}_q$, under certain structural restrictions, we prove a new explicit lower bound on the size of the product set $A(A + 1)$. Our result improves on the previous best known bound due to Zhelezov and holds under more relaxed restrictions.

Find SimilarView on arXiv

Difference sets are not multiplicatively closed

February 7, 2016

88% Match
Ilya D. Shkredov
Number Theory
Combinatorics

We prove that for any finite set A of real numbers its difference set D:=A-A has large product set and quotient set, namely, |DD|, |D/D| \gg |D|^{1+c}, where c>0 is an absolute constant. A similar result takes place in the prime field F_p for sufficiently small D. It gives, in particular, that multiplicative subgroups of size less than p^{4/5-\eps} cannot be represented in the form A-A for any A from F_p.

Find SimilarView on arXiv

A sum-product estimate in finite fields, and applications

January 29, 2003

87% Match
Jean Bourgain, Nets Katz, Terence Tao
Combinatorics
Number Theory

Let $A$ be a subset of a finite field $F := \Z/q\Z$ for some prime $q$. If $|F|^\delta < |A| < |F|^{1-\delta}$ for some $\delta > 0$, then we prove the estimate $|A+A| + |A.A| \geq c(\delta) |A|^{1+\eps}$ for some $\eps = \eps(\delta) > 0$. This is a finite field analogue of a result of Erdos and Szemeredi. We then use this estimate to prove a Szemeredi-Trotter type theorem in finite fields, and obtain a new estimate for the Erdos distance problem in finite fields, as well as...

Find SimilarView on arXiv

Additive properties of product sets in an arbitrary finite field

January 14, 2008

87% Match
Alexey Glibichuk
Number Theory
Combinatorics

It is proved that for any two subsets $A$ and $B$ of an arbitrary finite field $\Fq$ such that $|A||B|>q$ the identity $16AB=\Fq$ holds. Moreover, it is established that for every subsets $X, Y\subset \Fq$ with the property $|X||Y|\geqslant 2q$ the equality $8XY=\Fq$ holds.

Find SimilarView on arXiv

Slightly improved sum-product estimates in fields of prime order

July 12, 2009

87% Match
Liangpan Li
Number Theory
Combinatorics

Let $\mathbb{F}_p$ be the field of residue classes modulo a prime number $p$ and let $A$ be a nonempty subset of $\mathbb{F}_p$. In this paper we show that if $|A|\preceq p^{0.5}$, then \[ \max\{|A\pm A|,|AA|\}\succeq|A|^{13/12};\] if $|A|\succeq p^{0.5}$, then \[ \max\{|A\pm A|,|AA|\}\succapprox \min\{|A|^{13/12}(\frac{|A|}{p^{0.5}})^{1/12},|A|(\frac{p}{|A|})^{1/11}\}.\] These results slightly improve the estimates of Bourgain-Garaev and Shen. Sum-product estimates on differ...

Find SimilarView on arXiv

An improved sum-product estimate over finite fields

May 31, 2011

86% Match
Liangpan Li, Oliver Roche-Newton
Combinatorics

This paper gives an improved sum-product estimate for subsets of a finite field whose order is not prime. It is shown, under certain conditions, that $$\max\{|A+A|,|A\cdot{A}|\}\gg{\frac{|A|^{12/11}}{(\log_2|A|)^{5/11}}}.$$ This new estimate matches, up to a logarithmic factor, the current best known bound obtained over prime fields by Rudnev (\cite{mishaSP}).

Find SimilarView on arXiv

Arithmetic and Geometric Progressions in Productsets over Finite Fields

November 12, 2007

86% Match
Igor E. Shparlinski
Number Theory
Combinatorics

Given two sets $\cA, \cB \subseteq \F_q$ of elements of the finite field $\F_q$ of $q$ elements, we show that the productset $$ \cA\cB = \{ab | a \in \cA, b \in\cB\} $$ contains an arithmetic progression of length $k \ge 3$ provided that $k<p$, where $p$ is the characteristic of $\F_q$, and $# \cA # \cB \ge 3q^{2d-2/k}$. We also consider geometric progressions in a shifted productset $\cA\cB +h$, for $f \in \F_q$, and obtain a similar result.

Find SimilarView on arXiv