ID: 1601.04754

Prescribing the binary digits of squarefree numbers and quadratic residues

January 18, 2016

View on ArXiv
R. Dietmann, C. Elsholtz, I. E. Shparlinski
Mathematics
Number Theory

We study the equidistribution of multiplicatively defined sets, such as the squarefree integers, quadratic non-residues or primitive roots, in sets which are described in an additive way, such as sumsets or Hilbert cubes. In particular, we show that if one fixes any proportion less than $40\%$ of the digits of all numbers of a given binary bit length, then the remaining set still has the asymptotically expected number of squarefree integers. Next, we investigate the distribution of primitive roots modulo a large prime $p$, establishing a new upper bound on the largest dimension of a Hilbert cube in the set of primitive roots, improving on a previous result of the authors. Finally, we study sumsets in finite fields and asymptotically find the expected number of quadratic residues and non-residues in such sumsets, given their cardinalities are big enough. This significantly improves on a recent result by Dartyge, Mauduit and S\'ark\"ozy. Our approach introduces several new ideas, combining a variety of methods, such as bounds of exponential and character sums, geometry of numbers and additive combinatorics.

Similar papers 1

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.

Multiplicative Properties of Hilbert Cubes

January 3, 2022

85% Match
Igor E. Shparlinski
Number Theory
Combinatorics

We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large product sets and reciprocals of sum sets. In particular, our results replace recent estimates of N. Hegyv\'ari and P. P. Pach (2020), which appear to be void for all admissible parameters. Our approach is different from that of N. Hegyv\'ari and P. P. Pach and is based on some well-known bounds of double character and exponential sums over arbitrary sets, due to A. A. Karatsuba (199...

Find SimilarView on arXiv

Extremal problems and the combinatorics of sumsets

October 27, 2023

84% Match
Melvyn B. Nathanson
Number Theory

This is a survey of old and new problems and results in additive number theory.

Find SimilarView on arXiv

Solution-free sets for sums of binary forms

October 10, 2011

84% Match
Sean Prendiville
Number Theory

We obtain quantitative estimates for the asymptotic density of subsets of the two-dimensional integer lattice which contain only trivial solutions to an additive equation involving binary forms. In the process we develop an analogue of Vinogradov's mean value theorem applicable to binary forms.

Find SimilarView on arXiv

Inverse questions for the large sieve

November 24, 2013

84% Match
Ben J. Green, Adam J. Harper
Number Theory

Suppose that an infinite set $A$ occupies at most $\frac{1}{2}(p+1)$ residue classes modulo $p$, for every sufficiently large prime $p$. The squares, or more generally the integer values of any quadratic, are an example of such a set. By the large sieve inequality the number of elements of $A$ that are at most $X$ is $O(X^{1/2})$, and the quadratic examples show that this is sharp. The simplest form of the inverse large sieve problem asks whether they are the only examples. W...

Find SimilarView on arXiv

On square-free numbers generated from given sets of primes II

January 6, 2023

84% Match
Gábor Román
Number Theory

We progress with the investigation started in article \cite{Roman2022}, namely the analysis of the asymptotic behaviour of $Q_{\mathcal{P}}(x)$ for different sets $\mathcal{P}$, where $Q_{\mathcal{P}}(x)$ is the element count of the set containing those positive square-free integers, which are smaller than-, or equal to $x$, and which are only divisible by the elements of $\mathcal{P}$. We study how $Q_{\mathcal{P}}(x)$ behaves when we require that $\chi(p) = 1$ must hold for...

Find SimilarView on arXiv

Distribution of squares modulo a composite number

February 17, 2015

83% Match
Farzad Aryan
Number Theory

In this paper we study the distribution of squares modulo a square-free number $q$. We also look at inverse questions for the large sieve in the distribution aspect and we make improvements on existing results on the distribution of $s$-tuples of reduced residues.

Find SimilarView on arXiv

On sumsets involving $k$th power residues

April 24, 2023

83% Match
Hai-Liang Wu, Ning-Liu Wei, Yu-Bo Li
Number Theory

In this paper, we study some topics concerning the additive decompositions of the set $D_k$ of all $k$th power residues modulo a prime $p$. For example, given a positive integer $k\ge2$, we prove that $$\lim_{x\rightarrow+\infty}\frac{B(x)}{\pi(x)}=0,$$ where $\pi(x)$ is the number of primes $p\le x$ and $B(x)$ denotes the cardinality of the set $$\{p\le x: p\equiv1\pmod k; D_k\ \text{has a non-trivial 2-additive decomposition}\}.$$

Find SimilarView on arXiv

On primitive elements in finite fields of low characteristic

December 20, 2014

83% Match
Abhishek Bhowmick, Thái Hoàng Lê
Number Theory
Computational Complexity

We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$, small $q$ and large $n$, we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in...

Find SimilarView on arXiv

On the distribution of sparse sequences in prime fields and applications

August 25, 2010

83% Match
Victor C. Garcia
Number Theory

In the present paper we investigate distributional properties of sparse sequences modulo almost all prime numbers. We obtain new results for a wide class of sparse sequences which in particular find applications on additive problems and the discrete Littlewood problem related to lower bound estimates of the $L_1$-norm of trigonometric sums.

Find SimilarView on arXiv