BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ben Green

Ben Green appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NTmath.COmath.GRcs.CYmath.DSArtificial Intelligencemath.CAHuman-Computer InteractionMachine Learningmath.AGmath.MG

Catalog footprint

What is connected

43works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

43 published item(s)

preprint2024arXiv

New bounds for Szemeredi's theorem, II: A new bound for $r_4(N)$

Define $r_4(N)$ to be the largest cardinality of a set $A$ in $\{1,\dots,N\}$ which does not contain four elements in arithmetic progression. In 1998 Gowers proved that $r_4(N) \ll N(\log \log N)^{-c}$ for some absolute constant $c> 0$. In this paper (part II of a series) we improve this to $r_4(N) \ll N e^{-c\sqrt{\log \log N}}$. In part III of the series we will use a more elaborate argument to improve this to $r_4(N) \ll N(\log N)^{-c}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

"If it didn't happen, why would I change my decision?": How Judges Respond to Counterfactual Explanations for the Public Safety Assessment

Many researchers and policymakers have expressed excitement about algorithmic explanations enabling more fair and responsible decision-making. However, recent experimental studies have found that explanations do not always improve human use of algorithmic advice. In this study, we shed light on how people interpret and respond to counterfactual explanations (CFEs) -- explanations that show how a model's output would change with marginal changes to its input(s) -- in the context of pretrial risk assessment instruments (PRAIs). We ran think-aloud trials with eight sitting U.S. state court judges, providing them with recommendations from a PRAI that includes CFEs. We found that the CFEs did not alter the judges' decisions. At first, judges misinterpreted the counterfactuals as real -- rather than hypothetical -- changes to defendants. Once judges understood what the counterfactuals meant, they ignored them, stating their role is only to make decisions regarding the actual defendant in question. The judges also expressed a mix of reasons for ignoring or following the advice of the PRAI without CFEs. These results add to the literature detailing the unexpected ways in which people respond to algorithms and explanations. They also highlight new challenges associated with improving human-algorithm collaborations through explanations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Data Science as Political Action: Grounding Data Science in a Politics of Justice

In response to public scrutiny of data-driven algorithms, the field of data science has adopted ethics training and principles. Although ethics can help data scientists reflect on certain normative aspects of their work, such efforts are ill-equipped to generate a data science that avoids social harms and promotes social justice. In this article, I argue that data science must embrace a political orientation. Data scientists must recognize themselves as political actors engaged in normative constructions of society and evaluate their work according to its downstream impacts on people's lives. I first articulate why data scientists must recognize themselves as political actors. In this section, I respond to three arguments that data scientists commonly invoke when challenged to take political positions regarding their work. In confronting these arguments, I describe why attempting to remain apolitical is itself a political stance--a fundamentally conservative one--and why data science's attempts to promote "social good" dangerously rely on unarticulated and incrementalist political assumptions. I then propose a framework for how data science can evolve toward a deliberative and rigorous politics of social justice. I conceptualize the process of developing a politically engaged data science as a sequence of four stages. Pursuing these new approaches will empower data scientists with new methods for thoughtfully and rigorously contributing to social justice.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

New lower bounds for van der Waerden numbers

We show that there is a red-blue colouring of $[N]$ with no blue 3-term arithmetic progression and no red arithmetic progression of length $e^{C(\log N)^{3/4}(\log \log N)^{1/4}}$. Consequently, the two-colour van der Waerden number $w(3,k)$ is bounded below by $k^{b(k)}$, where $b(k) = c \big( \frac{\log k}{\log\log k} \big)^{1/3}$. Previously it had been speculated, supported by data, that $w(3,k) = O(k^2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Technology Ethics in Action: Critical and Interdisciplinary Perspectives

This special issue interrogates the meaning and impacts of "tech ethics": the embedding of ethics into digital technology research, development, use, and governance. In response to concerns about the social harms associated with digital technologies, many individuals and institutions have articulated the need for a greater emphasis on ethics in digital technology. Yet as more groups embrace the concept of ethics, critical discourses have emerged questioning whose ethics are being centered, whether "ethics" is the appropriate frame for improving technology, and what it means to develop "ethical" technology in practice. This interdisciplinary issue takes up these questions, interrogating the relationships among ethics, technology, and society in action. This special issue engages with the normative and contested notions of ethics itself, how ethics has been integrated with technology across domains, and potential paths forward to support more just and egalitarian technology. Rather than starting from philosophical theories, the authors in this issue orient their articles around the real-world discourses and impacts of tech ethics--i.e., tech ethics in action.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Contestation of Tech Ethics: A Sociotechnical Approach to Technology Ethics in Practice

This article introduces the special issue "Technology Ethics in Action: Critical and Interdisciplinary Perspectives". In response to recent controversies about the harms of digital technology, discourses and practices of "tech ethics" have proliferated across the tech industry, academia, civil society, and government. Yet despite the seeming promise of ethics, tech ethics in practice suffers from several significant limitations: tech ethics is vague and toothless, has a myopic focus on individual engineers and technology design, and is subsumed into corporate logics and incentives. These limitations suggest that tech ethics enables corporate "ethics-washing": embracing the language of ethics to defuse criticism and resist government regulation, without committing to ethical behavior. Given these dynamics, I describe tech ethics as a terrain of contestation where the central debate is not whether ethics is desirable, but what "ethics" entails and who gets to define it. Current approaches to tech ethics are poised to enable technologists and technology companies to label themselves as "ethical" without substantively altering their practices. Thus, those striving for structural improvements in digital technologies must be mindful of the gap between ethics as a mode of normative inquiry and ethics as a practical endeavor. In order to better evaluate the opportunities and limits of tech ethics, I propose a sociotechnical approach that analyzes tech ethics in light of who defines it and what impacts it generates in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On the width of transitive sets: bounds on matrix coefficients of finite groups

We say that a finite subset of the unit sphere in $\mathbf{R}^d$ is transitive if there is a group of isometries which acts transitively on it. We show that the width of any transitive set is bounded above by a constant times $(\log d)^{-1/2}$. This is a consequence of the following result: If $G$ is a finite group and $ρ: G \rightarrow \mbox{U}_d(\mathbf{C})$ a unitary representation, and if $v \in \mathbf{C}^d$ is a unit vector, there is another unit vector $w \in \mathbf{C}^d$ such that \[ \sup_{g \in G} |\langle ρ(g) v, w \rangle| \leq (1 + c \log d)^{-1/2}.\] These results answer a question of Yufei Zhao. An immediate consequence of our result is that the diameter of any quotient $S(\mathbf{R}^d)/G$ of the unit sphere by a finite group $G$ of isometries is at least $π/2 - o_{d \rightarrow \infty}(1)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Weighted Prékopa-Leindler inequality and sumsets with quasicubes

We give a short, self-contained proof of two key results from a paper of four of the authors. The first is a kind of weighted discrete Prékopa-Leindler inequality. This is then applied to show that if $A, B \subseteq \mathbb{Z}^d$ are finite sets and $U$ is a subset of a "quasicube" then $|A + B + U| \geq |A|^{1/2} |B|^{1/2} |U|$. This result is a key ingredient in forthcoming work of the fifth author and Pälvölgyi on the sum-product phenomenon.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fourier uniformity on subspaces

Let $\mathbb{F}$ be a fixed finite field, and let $A \subset \mathbb{F}^n$. It is a well-known fact that there is a subspace $V \leq \mathbb{F}^n$, $\mbox{codim} V \ll_δ 1$, and an $x$, such that $A$ is $δ$-uniform when restricted to $x + V$ (that is, all non-trivial Fourier coefficients of $A$ restricted to $x + V$ have magnitude at most $δ$). We show that if $\mathbb{F} = \mathbb{F}_2$ then it is possible to take $x = 0$; that is, $A$ is $δ$-uniform on a subspace $V \leq \mathbb{F}^n$. We give an example to show that this is not necessarily possible when $\mathbb{F} = \mathbb{F}_3$. ADDED July 2016: shortly after this paper appeared on the arxiv, F. Manners showed us a rather short argument he had found in 2013, giving a better bound for our main theorem. We do not, therefore, intend to publish this note. The example over $\mathbb{F}_3$ may still be of interest to some readers and so we will not withdraw the paper from the arxiv.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the chromatic number of random Cayley graphs

Let G be an abelian group of cardinality N, where (N,6) = 1, and let A be a random subset of G. Form a graph Gamma_A on vertex set G by joining x to y if and only if x + y is in A. Then, almost surely as N tends to infinity, the chromatic number chi(Gamma_A) is at most (1 + o(1))N/2 log_2 N. This is asymptotically sharp when G = Z/NZ, N prime. Presented at the conference in honour of Bela Bollobas on his 70th birthday, Cambridge August 2013.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Large gaps between consecutive prime numbers

Let $G(X)$ denote the size of the largest gap between consecutive primes below $X$. Answering a question of Erdos, we show that $$G(X) \geq f(X) \frac{\log X \log \log X \log \log \log \log X}{(\log \log \log X)^2},$$ where $f(X)$ is a function tending to infinity with $X$. Our proof combines existing arguments with a random construction covering a set of primes by arithmetic progressions. As such, we rely on recent work on the existence and distribution of long arithmetic progressions consisting entirely of primes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the quantitative distribution of polynomial nilsequences - erratum

This is an erratum to 'On the quantitative distribution of polynomial nilsequences' [GT]. The proof of Theorem 8.6 of that paper, which claims a distribution result for multiparameter polynomial sequences on nilmanifolds, was incorrect. We provide two fixes for this issue here. First, we deduce the "equal sides" case $N_1 = \dots = N_t = N$ of [GT, Theorem 8.6] from the 1-parameter results in [GT]. This is the same basic mode of argument we attempted in the original paper, though the details are different. The equal sides case is the only one required in applications such as the proof of the inverse conjectures for the Gowers norms due to the authors and Ziegler. Second, we sketch a proof that [GT, Theorem 8.6] does in fact hold in its originally stated form, that is to say without the equal sides condition. To obtain this statement the entire argument of [GT] must be run in the context of multiparameter polynomial sequences $g : \mathbb{Z}^t \rightarrow G$ rather than 1-parameter sequences $g : \mathbb{Z} \rightarrow G$ as is currently done.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The quantitative behaviour of polynomial orbits on nilmanifolds

A theorem of Leibman asserts that a polynomial orbit $(g(1),g(2),g(3),\ldots)$ on a nilmanifold $G/Γ$ is always equidistributed in a union of closed sub-nilmanifolds of $G/Γ$. In this paper we give a quantitative version of Leibman's result, describing the uniform distribution properties of a finite polynomial orbit $(g(1),\ldots,g(N))$ in a nilmanifold. More specifically we show that there is a factorization $g = εg'γ$, where $ε(n)$ is "smooth", $γ(n)$ is periodic and "rational", and $(g'(a),g'(a+d),\ldots,g'(a + d(l-1)))$ is uniformly distributed (up to a specified error $δ$) inside some subnilmanifold $G'/Γ'$ of $G/Γ$, for all sufficiently dense arithmetic progressions $a,a+d,\ldots,a+d(l-1)$ inside $\{1,..,N\}$. Our bounds are uniform in $N$ and are polynomial in the error tolerance delta. In a subsequent paper we shall use this theorem to establish the Mobius and Nilsequences conjecture from our earlier paper "Linear equations in primes".

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounded gaps between primes

These are notes on Zhang's work and subsequent developments produced in preparation for 5 hours of talks for a general mathematical audience given in Cambridge, Edinburgh and Auckland over the last year. Being for colloquium-style talks, these notes are at a much lower level than other accounts in the literature. In places they are deliberately quite nonrigorous. Whether anyone will find them helpful is unclear but some care was taken on their preparation and there is, I hope, little harm in making them available here.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Counting sets with small sumset and applications

We study the number of $k$-element sets $A \subset \{1,\ldots,N\}$ with $|A + A| \leq K|A|$ for some (fixed) $K > 0$. Improving results of the first author and of Alon, Balogh, Samotij and the second author, we determine this number up to a factor of $2^{o(k)} N^{o(1)}$ for most $N$ and $k$. As a consequence of this and a further new result concerning the number of sets $A \subset \mathbf{Z}/N\mathbf{Z}$ with $|A +A| \leq c |A|^2$, we deduce that the random Cayley graph on $\mathbf{Z}/N\mathbf{Z}$ with edge density~$\frac{1}{2}$ has no clique or independent set of size greater than $\big( 2 + o(1) \big) \log_2 N$, asymptotically the same as for the Erdős-Rényi random graph. This improves a result of the first author from 2003 in which a bound of $160 \log_2 N$ was obtained. As a second application, we show that if the elements of $A \subset \mathbf{N}$ are chosen at random, each with probability $1/2$, then the probability that $A+A$ misses exactly $k$ elements of $\mathbf{N}$ is equal to $\big( 2 + o(1) \big)^{-k/2}$ as $k \to \infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On sets defining few ordinary lines

Let P be a set of n points in the plane, not all on a line. We show that if n is large then there are at least n/2 ordinary lines, that is to say lines passing through exactly two points of P. This confirms, for large n, a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than n - C ordinary lines for some absolute constant C. We also solve, for large n, the "orchard-planting problem", which asks for the maximum number of lines through exactly 3 points of P. Underlying these results is a structure theorem which states that if P has at most Kn ordinary lines then all but O(K) points of P lie on a cubic curve, if n is sufficiently large depending on K.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New bounds for Szemeredi's theorem, Ia: Progressions of length 4 in finite field geometries revisited

Let p > 4 be a prime. We show that the largest subset of F_p^n with no 4-term arithmetic progressions has cardinality << N(log N)^{-c}, where c = 2^{-22} and N := p^n. A result of this type was claimed in a previous paper by the authors and published in Proc. London Math. Society. Unfortunately the proof had a gap, and we issue an erratum for that paper here. Our new argument is different and significantly shorter. In fact we prove a stronger result, which can be viewed as a quantatitive version of some previous results of Bergelson-Host-Kra and the authors.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On (not) computing the Mobius function using bounded depth circuits

Any function F : {0,...,N-1} -> {-1,1} such that F(x) can be computed from the binary digits of x using a bounded depth circuit is orthogonal to the Mobius function mu in the sense that E_{0 <= x <= N-1} mu(x)F(x) = o(1). The proof combines a result of Linial, Mansour and Nisan with techniques of Katai and Harman-Katai, used in their work on finding primes with specified digits.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An inverse theorem for the Gowers U^{s+1}[N]-norm (announcement)

In this note we announce the proof of the inverse conjecture for the Gowers U^{s+1}[N]-norm for all s => 3; this is new for s => 4, the cases s = 1,2,3 having been previously established. More precisely we outline a proof (details of which will appear in a forthcoming paper) that if f : [N] -> [-1,1] is a function with || f ||_{U^{s+1}[N]} => δthen there is a bounded-complexity s-step nilsequence F(g(n)Γ) which correlates with f, where the bounds on the complexity and correlation depend only on s and δ. From previous results, this conjecture implies the Hardy-Littlewood prime tuples conjecture for any linear system of finite complexity. In particular, one obtains an asymptotic formula for the number of k-term arithmetic progressions p_1 < p_2 < ... < p_k <= N of primes, for every k => 3.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Contractions and expansion

Let A be a finite set of reals and let K >= 1 be a real number. Suppose that for each a in A we are given an injective map f_a : A -> R which fixes a and contracts other points towards it in the sense that |a - f_a(x)| <= |a - x|/K for all x in A, and such that f_a(x) always lies between a and x. Then the union of the f_a(A) has cardinality >= K|A|/10 - O_K(1). An immediate consequence of this is the estimate |A + K.A| >= K|A|/10 - O_K(1), which is a slightly weakened version of a result of Bukh.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Strongly dense free subgroups of semisimple algebraic groups

We show that (with one possible exception) there exist strongly dense free subgroups in any semisimple algebraic group over a large enough field. These are nonabelian free subgroups all of whose subgroups are either cyclic or Zariski dense. As a consequence, we get new generating results for finite simple groups of Lie type and a strengthening of a theorem of Borel related to the Hausdorff-Banach-Tarski paradox. In a sequel to this paper, we use this result to also establish uniform expansion properties for random Cayley graphs over finite simple groups of Lie type.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Mobius function is strongly orthogonal to nilsequences

We show that the Mobius function mu(n) is strongly asymptotically orthogonal to any polynomial nilsequence n -> F(g(n)L). Here, G is a simply-connected nilpotent Lie group with a discrete and cocompact subgroup L (so G/L is a nilmanifold), g : Z -> G is a polynomial sequence and F: G/L -> R is a Lipschitz function. More precisely, we show that the inner product of mu(n) with F(g(n)L) over {1,...,N} is bounded by 1/log^A N, for all A > 0. In particular, this implies the Mobius and Nilsequence conjecture MN(s) from our earlier paper "Linear equations in primes" for every positive integer s. This is one of two major ingredients in our programme, outlined in that paper, to establish a large number of cases of the generalised Hardy-Littlewood conjecture, which predicts how often a collection ψ_1,...,ψ_t : Z^d -> Z of linear forms all take prime values. The proof is a relatively quick application of the results in our recent companion paper on the distribution of polynomial orbits on nilmanifolds. We give some applications of our main theorem. We show, for example, that the Mobius function is uncorrelated with any bracket polynomial. We also obtain a result about the distribution of nilsequences n -> a^nxL as n ranges only over the primes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The structure of approximate groups

Let K >= 1 be a parameter. A K-approximate group is a finite set A in a (local) group which contains the identity, is symmetric, and such that A^2 is covered by K left translates of A. The main result of this paper is a qualitative description of approximate groups as being essentially finite-by-nilpotent, answering a conjecture of H. Helfgott and E. Lindenstrauss. This may be viewed as a generalisation of the Freiman-Ruzsa theorem on sets of small doubling in the integers to arbitrary groups. We begin by establishing a correspondence principle between approximate groups and locally compact (local) groups that allows us to recover many results recently established in a fundamental paper of Hrushovski. In particular we establish that approximate groups can be approximately modeled by Lie groups. To prove our main theorem we apply some additional arguments essentially due to Gleason. These arose in the solution of Hilbert's fifth problem in the 1950s. Applications of our main theorem include a finitary refinement of Gromov's theorem, as well as a generalized Margulis lemma conjectured by Gromov and a result on the virtual nilpotence of the fundamental group of Ricci almost nonnegatively curved manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An inverse theorem for the Gowers U^4 norm

We prove the so-called inverse conjecture for the Gowers U^{s+1}-norm in the case s = 3 (the cases s < 3 being established in previous literature). That is, we establish that if f : [N] -> C is a function with |f(n)| <= 1 for all n and || f ||_{U^4} >= δthen there is a bounded complexity 3-step nilsequence F(g(n)Γ) which correlates with f. The approach seems to generalise so as to prove the inverse conjecture for s >= 4 as well, and a longer paper will follow concerning this. By combining this with several previous papers of the first two authors one obtains the generalised Hardy-Littlewood prime-tuples conjecture for any linear system of complexity at most 3. In particular, we have an asymptotic for the number of 5-term arithmetic progressions p_1 < p_2 < p_3 < p_4 < p_5 <= N of primes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Approximate subgroups of linear groups

We establish various results on the structure of approximate subgroups in linear groups such as SL_n(k) that were previously announced by the authors. For example, generalising a result of Helfgott (who handled the cases n = 2 and 3), we show that any approximate subgroup of SL_n(F_q) which generates the group must be either very small or else nearly all of SL_n(F_q). The argument generalises to other absolutely almost simple connected (and non-commutative) algebraic groups G over a finite field k. In a subsequent paper, we will give applications of this result to the expansion properties of Cayley graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Linear Approximate Groups

This is an informal announcement of results to be described and proved in detail in a paper to appear. We give various results on the structure of approximate subgroups in linear groups such as $\SL_n(k)$. For example, generalising a result of Helfgott (who handled the cases $n = 2$ and 3), we show that any approximate subgroup of $\SL_n(\F_q)$ which generates the group must be either very small or else nearly all of $\SL_n(\F_q)$. The argument is valid for all Chevalley groups $G(\F_q)$.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm

We establish a correspondence between inverse sumset theorems (which can be viewed as classifications of approximate (abelian) groups) and inverse theorems for the Gowers norms (which can be viewed as classifications of approximate polynomials). In particular, we show that the inverse sumset theorems of Freiman type are equivalent to the known inverse results for the Gowers U^3 norms, and moreover that the conjectured polynomial strengthening of the former is also equivalent to the polynomial strengthening of the latter. We establish this equivalence in two model settings, namely that of the finite field vector spaces F_2^n, and of the cyclic groups Z/NZ. In both cases the argument involves clarifying the structure of certain types of approximate homomorphism.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

New bounds for Szemeredi's Theorem, I: Progressions of length 4 in finite field geometries

Let F be a fixed finite field of characteristic at least 5. Let G = F^n be the n-dimensional vector space over F, and write N := |G|. We show that if A is a subset of G with size at least c_F N(log N)^{-c}, for some absolute constant c > 0 and some c_F > 0, then A contains four distinct elements in arithmetic progression. This is equivalent, in the usual notation of additive combinatorics, to the assertion that r_4(G) <<_F N(log N)^{-c}.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

A quantitative version of the idempotent theorem in harmonic analysis

Suppose that G is a locally compact abelian group, and write M(G) for the algebra of bounded, regular, complex-valued measures under convolution. A measure μin M(G) is said to be idempotent if μ* μ= μ, or alternatively if the Fourier-Stieltjes transform μ^ takes only the values 0 and 1. The Cohen-Helson-Rudin idempotent theorem states that a measure μis idempotent if and only if the set {r in G^ : μ^(r) = 1} belongs to the coset ring of G^, that is to say we may write μ^ as a finite plus/minus 1 combination of characteristic functions of cosets r_j + H_j, where the H_j are open subgroups of G^. In this paper we show that the number L of such cosets can be bounded in terms of the norm ||μ||, and in fact one may take L <= \exp\exp(C||μ||^4). In particular our result is non-trivial even for finite groups.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

On the maximal number of three-term arithmetic progressions in subsets of Z/pZ

Let a be a real number between 0 and 1. Ernie Croot showed that the quantity \max_A #(3-term arithmetic progressions in A)/p^2, where A ranges over all subsets of Z/pZ of size at most a*p, tends to a limit as p tends to infinity through primes. Writing c(a) for this limit, we show that c(a) = a^2/2 provided that a is smaller than some absolute constant. In fact we prove rather more, establishing a structure theorem for sets having the maximal number of 3-term progressions amongst all subsets of Z/pZ of cardinality m, provided that m < c*p.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Quadratic Uniformity of the Mobius Function

This paper is a part of our programme to generalise the Hardy-Littlewood method to handle systems of linear questions in primes. This programme is laid out in our paper Linear Equations in Primes [LEP], which accompanies this submission. In particular, the results of this paper may be used, together with the machinery of [LEP], to establish an asymptotic for the number of four-term progressions p_1 < p_2 < p_3 < p_4 <= N of primes, and more generally any problem counting prime points inside a ``non-degenerate'' affine lattice of codimension at most 2. The main result of this paper is a proof of the Mobius and Nilsequences Conjecture for 1 and 2-step nilsequences. This conjecture is introduced in [LEP] and amounts to showing that if G/Γis an s-step nilmanifold, s <= 2, if F : G/Γ-> [-1,1] is a Lipschitz function, and if T_g : G/Γ-> G/Γis the action of g \in G on G/Γ, then the Mobius function μ(n) is orthogonal to the sequence F(T_g^n x) in a fairly strong sense, uniformly in g and x in G/Γ. This can be viewed as a ``quadratic'' generalisation of an exponential sum estimate of Davenport, and is proven by the following the methods of Vinogradov and Vaughan.

0 citations0 reviewsNo code linkedOpen access