ID: 1601.04754

Prescribing the binary digits of squarefree numbers and quadratic residues

January 18, 2016

View on ArXiv

Similar papers 2

Counting Additive Decompositions of Quadratic Residues in Finite Fields

March 11, 2014

83% Match
Simon R. Blackburn, Sergei V. Konyagin, Igor E. 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\}$. 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.

Find SimilarView on arXiv

On RSA Moduli with Almost Half of the Bits Prescribed

September 17, 2007

83% Match
Sidney W. Graham, Igor E. Shparlinski
Number Theory

We show that using character sum estimates due to H. Iwaniec leads to an improvement of recent results about the distribution and finding RSA moduli $M=pl$, where $p$ and $l$ are primes, with prescribed bit patterns. We are now able to specify about $n$ bits instead of about $n/2$ bits as in the previous work. We also show that the same result of H. Iwaniec can be used to obtain an unconditional version of a combinatorial result of W. de Launey and D. Gordon that was original...

Find SimilarView on arXiv

Arithmetic structures in random sets

March 26, 2007

82% Match
Mariah Hamel, Izabella Laba
Number Theory
Combinatorics

We extend two well-known results in additive number theory, S\'ark\"ozy's theorem on square differences in dense sets and a theorem of Green on long arithmetic progressions in sumsets, to subsets of random sets of asymptotic density 0. Our proofs rely on a restriction-type Fourier analytic argument of Green and Green-Tao.

Find SimilarView on arXiv

The additive structure of the squares inside rings

November 4, 2016

82% Match
David Cushing, G. W. Stagg
Combinatorics
Number Theory

When defining the amount of additive structure on a set it is often convenient to consider certain sumsets; Calculating the cardinality of these sumsets can elucidate the set's underlying structure. We begin by investigating finite sets of perfect squares and associated sumsets. We reveal how arithmetic progressions efficiently reduce the cardinality of sumsets and provide estimates for the minimum size, taking advantage of the additive structure that arithmetic progressions ...

Find SimilarView on arXiv

On sets of large exponential sums

May 26, 2006

82% Match
I. D. Shkredov
Number Theory
Combinatorics

Let A be a subset of Z / NZ, and let R be the set of large Fourier coefficients of A. Properties of R have been studied in works of M.-C. Chang and B. Green. Our result is the following : the number of quadruples (r_1, r_2, r_3, r_4) \in R^4 such that r_1 + r_2 = r_3 + r_4 is at least |R|^{2+\epsilon}, \epsilon>0. This statement shows that the set R is highly structured. We also discuss some of the generalizations and applications of our result.

Find SimilarView on arXiv

Partitio Numerorum: sums of squares and higher powers

February 14, 2024

82% Match
Joerg Bruedern, Trevor D. Wooley
Number Theory

We survey the potential for progress in additive number theory arising from recent advances concerning major arc bounds associated with mean value estimates for smooth Weyl sums. We focus attention on the problem of representing large positive integers as sums of a square and a number of $k$-th powers. We show that such representations exist when the number of $k$-th powers is at least $\lfloor c_0k\rfloor +2$, where $c_0=2.136294\ldots $. By developing an abstract framework ...

Find SimilarView on arXiv

Equal sums in random sets and the concentration of divisors

August 1, 2019

82% Match
Kevin Ford, Ben Green, Dimitris Koukoulopoulos
Number Theory
Combinatorics

We study the extent to which divisors of a typical integer $n$ are concentrated. In particular, defining the Erd\H{o}s-Hooley $\Delta$-function by $\Delta(n) := \max_t \# \{d | n, \log d \in [t,t+1]\}$, we show that $\Delta(n) \geq (\log \log n)^{0.35332277\dots}$ for almost all $n$, a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over...

Find SimilarView on arXiv

On squares in special sets of finite fields

February 21, 2016

82% Match
Mikhail Gabdullin
Number Theory

We consider the linear vector space formed by the elements of the finite fields $\mathbb{F}_q$ with $q=p^r$ over $\mathbb{F}_p$. Let $\{a_1,\ldots,a_r\}$ be a basis of this space. Then the elements $x$ of $\mathbb{F}_q$ have a unique representation in the form $\sum_{j=1}^r c_ja_j$ with $c_j\in\mathbb{F}_p$. Let $D_1,\ldots,D_r$ be subsets of $\mathbb{F}_p$. We consider the set $W=W(D_1,\ldots,D_r)$ of elements of $\mathbb{F}_q$ such that $c_j \in D_j$ for all $j=1,\ldots,r$....

Find SimilarView on arXiv

Problems in Additive Number Theory, III: Thematic Seminars at the Centre de Recerca Matematica

July 14, 2008

82% Match
Melvyn B. Nathanson
Number Theory
Combinatorics

This is a survey of open problems in different parts of combinatorial and additive number theory. The paper is based on lectures at the Centre de Recerca Matematica in Barcelona on January 23 and January 25, 2008.

Find SimilarView on arXiv

A note on cube-free problems

November 21, 2023

82% Match
Yuchen Meng
Combinatorics

Eberhard and Pohoata conjectured that every $3$-cube-free subset of $[N]$ has size less than $2N/3+o(N)$. In this paper we show that if we replace $[N]$ with $\mathbb{Z}_N$ the upper bound of $2N/3$ holds, and the bound is tight when $N$ is divisible by $3$ since we have $A=\{a\in \mathbb{Z}_N:a\equiv 1,2\pmod{3}\}.$ Inspired by this observation we conjecture that every $d$-cube-free subset of $\mathbb{Z}_N$ has size less than $(d-1)N/d$ where $N$ is divisible by $d$, and we ...

Find SimilarView on arXiv