ID: 1403.2589

Counting Additive Decompositions of Quadratic Residues in Finite Fields

March 11, 2014

View on ArXiv
Simon R. Blackburn, Sergei V. Konyagin, Igor E. Shparlinski
Mathematics
Number Theory
Combinatorics

We say that a set $S$ is additively decomposed into two sets $A$ and $B$ if $S = \{a+b : a\in A, \ b \in B\}$. A. S\'ark\"ozy has recently conjectured that the set $Q$ of quadratic residues modulo a prime $p$ does not have nontrivial decompositions. Although various partial results towards this conjecture have been obtained, it is still open. Here we obtain a nontrivial upper bound on the number of such decompositions.

Similar papers 1

Additive Decompositions of Subgroups of Finite Fields

January 14, 2013

91% Match
Igor Shparlinski
Number Theory
Combinatorics

We say that a set $S$ is additively decomposed into two sets $A$ and $B$, if $S = \{a+b : a\in A, \ b \in B\}$. Here we study additively decompositions of multiplicative subgroups of finite fields. In particular, we give some improvements and generalisations of results of C. Dartyge and A. Sarkozy on additive decompositions of quadratic residues and primitive roots modulo $p$. We use some new tools such the Karatsuba bound of double character sums and some results from additi...

Find SimilarView on arXiv

Additive decompositions of large multiplicative subgroups in finite fields

April 26, 2023

90% Match
Chi Hoi Yip
Number Theory

We show that a large multiplicative subgroup of a finite field $\mathbb{F}_q$ cannot be decomposed into $A+A$ or $A+B+C$ nontrivially. We also find new families of multiplicative subgroups that cannot be decomposed as the sum of two sets nontrivially. In particular, our results extensively generalize the results of S\'{a}rk\"{o}zy and Shkredov on the additive decomposition of the set of quadratic residues modulo a prime.

Find SimilarView on arXiv

A conjecture of S\'ark\"ozy on quadratic residues, II

February 6, 2022

90% Match
Yong-Gao Chen, Ping Xi
Number Theory

Denote by $\mathcal{R}_p$ the set of all quadratic residues in $\mathbf{F}_p$ for each prime $p$. A conjecture of A. S\'ark\"ozy asserts, for all sufficiently large $p$, that no subsets $\mathcal{A},\mathcal{B}\subseteq\mathbf{F}_p$ with $|\mathcal{A}|,|\mathcal{B}|\geqslant2$ satisfy $\mathcal{A}+\mathcal{B}=\mathcal{R}_p$. In this paper, we show that if such subsets $\mathcal{A},\mathcal{B}$ do exist, then there are at least $(\log 2)^{-1}\sqrt p-1.6$ elements in $\mathcal{...

Find SimilarView on arXiv

On additive decompositions of primitive elements in finite fields

February 10, 2022

88% Match
Hai-Liang Wu, Yue-Feng She
Number Theory

In this paper, we study several topics on additive decompositions of primitive elemements in finite fields. Also we refine some bounds obtained by Dartyge and S\'{a}rk\"{o}zy and Shparlinski.

Find SimilarView on arXiv
Ilya D. Shkredov
Number Theory
Combinatorics

In our paper, we apply additive-combinatorial methods to study the distribution of the set of squares $\mathcal{R}$ in the prime field. We obtain the best upper bound on the number of gaps in $\mathcal{R}$ at the moment and generalize this result for sets with small doubling.

Additive decompositions induced by multiplicative characters over finite fields

July 7, 2011

87% Match
Davide Schipani, Michele Elia
Number Theory

In 1952, Perron showed that quadratic residues in a field of prime order satisfy certain ad- ditive properties. This result has been generalized in different directions, and our contribution is to provide a further generalization concerning multiplicative quadratic and cubic characters over any finite field. In particular, recalling that a character partitions the multiplicative group of the field into cosets with respect to its kernel, we will derive the number of representa...

Find SimilarView on arXiv

Bounds on the cardinality of restricted sumsets in $\mathbb{Z}_{p}$

March 26, 2018

87% Match
Gabriel Bengochea, Bernardo Llano
Combinatorics

In this paper we present a procedure which allows to transform a subset $A$ of $\mathbb{Z}_{p}$ into a set $ A'$ such that $ |2\hspace{0.15cm}\widehat{} A'|\leq|2\hspace{0.15cm}\widehat{} A | $, where $2\hspace{0.15cm}\widehat{} A$ is defined to be the set $\left\{a+b:a\neq b,\;a,b\in A\right\}$. From this result, we get some lower bounds for $ |2\hspace{0.15cm}\widehat{} A| $. Finally, we give some remarks related to the problem for which sets $A\subset \mathbb{Z}_{p}$ we ha...

Find SimilarView on arXiv

Squares and difference sets in finite fields

May 2, 2013

87% Match
Christine Bachoc, Imre Z. Ruzsa, Mate Matolcsi
Combinatorics
Number Theory

For infinitely many primes $p=4k+1$ we give a slightly improved upper bound for the maximal cardinality of a set $B\subset \ZZ_p$ such that the difference set $B-B$ contains only quadratic residues. Namely, instead of the "trivial" bound $|B|\leq \sqrt{p}$ we prove $|B|\leq \sqrt{p}-1$, under suitable conditions on $p$. The new bound is valid for approximately three quarters of the primes $p=4k+1$.

Find SimilarView on arXiv

Refined Estimates Concerning Sumsets Contained in the Roots of Unity

May 22, 2019

86% Match
Brandon Hanson, Giorgis Petridis
Number Theory
Combinatorics

We prove that the clique number of the Paley graph is at most $\sqrt{p/2} + 1$, and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets.

Find SimilarView on arXiv

Quadratic residues and difference sets

February 24, 2015

86% Match
Vsevolod F. Lev, Jack Sonn
Number Theory

It has been conjectured by Sarkozy that with finitely many exceptions, the set of quadratic residues modulo a prime $p$ cannot be represented as a sumset $\{a+b\colon a\in A, b\in B\}$ with non-singleton sets $A,B\subset F_p$. The case $A=B$ of this conjecture has been recently established by Shkredov. The analogous problem for differences remains open: is it true that for all sufficiently large primes $p$, the set of quadratic residues modulo $p$ is not of the form $\{a'-a"\...

Find SimilarView on arXiv