Source author record

Mark Lewko

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CA math.PR math.CO math.NT Distributed, Parallel, and Cluster Computing math-ph math.FA math.MP

Catalog footprint

Research overview

15works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Additive Energy and the Hausdorff dimension of the exceptional set in metric pair correlation problems

For a sequence of integers $\{a(x)\}_{x \geq 1}$ we show that the distribution of the pair correlations of the fractional parts of $\{ \langle αa(x) \rangle \}_{x \geq 1}$ is asymptotically Poissonian for almost all $α$ if the additive energy of truncations of the sequence has a power savings improvement over the trivial estimate. Furthermore, we give an estimate for the Hausdorff dimension of the exceptional set as a function of the density of the sequence and the power savings in the energy estimate. A consequence of these results is that the Hausdorff dimension of the set of $α$ such that $\{\langle αx^d \rangle\}$ fails to have Poissonian pair correlation is at most $\frac{d+2}{d+3} < 1$ . This strengthens a result of Rudnick and Sarnak which states that the exceptional set has zero Lebesgue measure. On the other hand, classical examples imply that the exceptional set has Hausdorff dimension at least $\frac{2}{d+1}$ . An appendix by Jean Bourgain was added after the first version of this paper was written. In this appendix two problems raised in the paper are solved.

preprint2016arXiv

Finite field restriction estimates based on Kakeya maximal operator estimates

In the finite field setting, we show that the restriction conjecture associated to any one of a large family of $d=2n+1$ dimensional quadratic surfaces implies the $n+1$ dimensional Kakeya conjecture (Dvir's theorem). This includes the case of the paraboloid over finite fields in which $-1$ \emph{is} a square. We are able to partially reverse this implication using the sharp Kakeya maximal operator estimates of Ellenberg, Oberlin and Tao to establish the first finite field restriction estimates beyond the Stein-Tomas exponent in this setting.

preprint2016arXiv

New Restriction Estimates for the 3-d Paraboloid over Finite Fields

We improve the range of exponents for the restriction problem for the 3-d paraboloid over finite fields. The key new ingredient is a variant of the Bourgain-Katz-Tao finite field incidence theorem derived from sum-product estimates. In prime order fields, we give an explicit relationship between the exponent in this incidence theorem and restriction estimates for the paraboloid.

preprint2016arXiv

Sidonicity and variants of Kaczmarz's problem

We prove that a uniformly bounded system of orthonormal functions satisfying the $ψ_2$ condition: (1) must contain a Sidon subsystem of proportional size, (2) must satisfy the Rademacher-Sidon property, and (3) must have its 5-fold tensor satisfy the Sidon property. On the other hand, we construct a uniformly bounded orthonormal system that satisfies the $ψ_2$ condition but which is not Sidon. These problems are variants of Kaczmarz's Scottish book problem (problem 130) which, in its original formulation, was answered negatively by Rudin. A corollary of our argument is a new, elementary proof of Pisier's theorem that a set of characters satisfying the $ψ_2$ condition is Sidon.

preprint2014arXiv

Refinements of Gál's theorem and applications

We give a simple proof of a well-known theorem of Gál and of the recent related results of Aistleitner, Berkes and Seip [1] regarding the size of GCD sums. In fact, our method obtains the asymptotically sharp constant in Gál's theorem, which is new. Our approach also gives a transparent explanation of the relationship between the maximal size of the Riemann zeta function on vertical lines and bounds on GCD sums; a point which was previously unclear. Furthermore we obtain sharp bounds on the spectral norm of GCD matrices which settles a question raised in [2]. We use bounds for the spectral norm to show that series formed out of dilates of periodic functions of bounded variation converge almost everywhere if the coefficients of the series are in $L^2 (\log\log 1/L)^γ$ , with $γ> 2$ . This was previously known with $γ>4$ , and is known to fail for $γ<2$ . We also develop a sharp Carleson-Hunt-type theorem for functions of bounded variations which settles another question raised in [1]. Finally we obtain almost sure bounds for partial sums of dilates of periodic functions of bounded variations improving [1]. This implies almost sure bounds for the discrepancy of $\{n_k x\}$ with $n_k$ an arbitrary growing sequences of integers.

preprint2013arXiv

Maximal Operators Associated to Multiplicative Characters

We show that the natural analogue of the Carleson-Hunt inequality fails for multiplicative characters.

preprint2013arXiv

On the Complexity of Asynchronous Agreement Against Powerful Adversaries

We introduce new techniques for proving lower bounds on the running time of randomized algorithms for asynchronous agreement against powerful adversaries. In particular, we define a \emph{strongly adaptive adversary} that is computationally unbounded and has a limited ability to corrupt a dynamic subset of processors by erasing their memories. We demonstrate that the randomized agreement algorithms designed by Ben-Or and Bracha to tolerate crash or Byzantine failures in the asynchronous setting extend to defeat a strongly adaptive adversary. These algorithms have essentially perfect correctness and termination, but at the expense of exponential running time. In the case of the strongly adaptive adversary, we show that this dismally slow running time is \emph{inherent}: we prove that any algorithm with essentially perfect correctness and termination against the strongly adaptive adversary must have exponential running time. We additionally interpret this result as yielding an enhanced understanding of the tools needed to simultaneously achieving perfect correctness and termination as well as fast running time for randomized algorithms tolerating crash or Byzantine failures.

preprint2012arXiv

A Variational Barban-Davenport-Halberstam Theorem

We prove variational forms of the Barban-Davenport-Halberstam Theorem and the large sieve inequality. We apply our result to prove an estimate for the sum of the squares of prime differences, averaged over arithmetic progressions.

preprint2012arXiv

Estimates for the Square Variation of Partial Sums of Fourier Series and their Rearrangements

We investigate the square variation operator $V^2$ (which majorizes the partial sum maximal operator) on general orthonormal systems (ONS) of size $N$ . We prove that the $L^2$ norm of the $V^2$ operator is bounded by $O(\ln(N))$ on any ONS. This result is sharp and refines the classical Rademacher-Menshov theorem. We show that this can be improved to $O(\sqrt{\ln(N)})$ for the trigonometric system, which is also sharp. We show that for any choice of coefficients, this truncation of the trigonometric system can be rearranged so that the $L^2$ norm of the associated $V^2$ operator is $O(\sqrt{\ln\ln(N)})$ . We also show that for $p>2$ , a bounded ONS of size $N$ can be rearranged so that the $L^2$ norm of the $V^p$ operator is at most $O_p(\ln \ln (N))$ uniformly for all choices of coefficients. This refines Bourgain's work on Garsia's conjecture, which is equivalent to the $V^{\infty}$ case. Several other results on operators of this form are also obtained. The proofs rely on combinatorial and probabilistic methods.

preprint2012arXiv

Orthonormal Systems in Linear Spans

We show that any $N$ -dimensional linear subspace of $L^2(\mathbb{T})$ admits an orthonormal system such that the $L^2$ norm of the square variation operator $V^2$ is as small as possible. When applied to the span of the trigonometric system, we obtain an orthonormal system of trigonometric polynomials with a $V^2$ operator that is considerably smaller than the associated operator for the trigonometric system itself.

preprint2012arXiv

The Square Variation of Rearranged Fourier Series

We prove that there exists a rearrangement of the first $N$ elements of the trigonometric system such that the $L^2$ -norm of the square variation operator is at most $O_ε(\log^{9/22+ε}(N))$ . This is an improvement over $O(\log^{1/2}(N))$ from the canonical ordering.

preprint2011arXiv

An Exact Asymptotic for the Square Variation of Partial Sum Processes

We establish an exact asymptotic formula for the square variation of certain partial sum processes. Let $\{X_{i}\}$ be a sequence of independent, identically distributed mean zero random variables with finite variance $σ$ and satisfying a moment condition $\mathbb{E}[|X_{i}|^{2+δ} ] < \infty$ for some $δ> 0$ . If we let $\mathcal{P}_{N}$ denote the set of all possible partitions of the interval $[N]$ into subintervals, then we have that $\max_{π\in \mathcal{P}_{N}} \sum_{I \in π} | \sum_{i\in I} X_{i}|^2 \sim 2 σ^2N \ln \ln(N)$ holds almost surely. This can be viewed as a variational strengthening of the law of the iterated logarithm and refines results of J. Qian on partial sum and empirical processes. When $δ= 0$ , we obtain a weaker `in probability' version of the result.

preprint2011arXiv

Endpoint restriction estimates for the paraboloid over finite fields

We prove certain endpoint restriction estimates for the paraboloid over finite fields in three and higher dimensions. Working in the bilinear setting, we are able to pass from estimates for characteristic functions to estimates for general functions while avoiding the extra logarithmic power of the field size which is introduced by the dyadic pigeonhole approach. This allows us to remove logarithmic factors from the estimates obtained by Mockenhaupt and Tao in three dimensions and those obtained by Iosevich and Koh in higher dimensions.

preprint2011arXiv

On the Structure of Sets of Large Doubling

We investigate the structure of finite sets $A \subseteq \Z$ where $|A+A|$ is large. We present a combinatorial construction that serves as a counterexample to natural conjectures in the pursuit of an "anti-Freiman" theory in additive combinatorics. In particular, we answer a question along these lines posed by O'Bryant. Our construction also answers several questions about the nature of finite unions of $B_2[g]$ and $B^\circ_2[g]$ sets, and enables us to construct a $Λ(4)$ set which does not contain large $B_2[g]$ or $B^\circ_2[g]$ sets.

preprint2010arXiv

An Improved Upper Bound for the Sum-free Subset Constant

We show that the optimal constant in Erdös' sum-free subset theorem cannot be larger than $11/28 \approx .393$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mark Lewko

Research overview

Is this your work?

15 publications

Additive Energy and the Hausdorff dimension of the exceptional set in metric pair correlation problems

Finite field restriction estimates based on Kakeya maximal operator estimates

New Restriction Estimates for the 3-d Paraboloid over Finite Fields

Sidonicity and variants of Kaczmarz's problem

Refinements of Gál's theorem and applications

Maximal Operators Associated to Multiplicative Characters

On the Complexity of Asynchronous Agreement Against Powerful Adversaries

A Variational Barban-Davenport-Halberstam Theorem

Estimates for the Square Variation of Partial Sums of Fourier Series and their Rearrangements

Orthonormal Systems in Linear Spans

The Square Variation of Rearranged Fourier Series

An Exact Asymptotic for the Square Variation of Partial Sum Processes

Endpoint restriction estimates for the paraboloid over finite fields

On the Structure of Sets of Large Doubling

An Improved Upper Bound for the Sum-free Subset Constant

See the researcher in context

Building this map preview