An official website of the United States government
In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without non-trivial three-term arithmetic progressions. In this work, we extend their result, establishing similar bounds for all linear patterns defined by binary systems of linear forms, where “binary” indicates that every linear form depends on exactly two variables. Prior to our work, no strong bounds were known for such systems even in the finite field model setting. A key ingredient in our proof is a graph counting lemma. The classical graph counting lemma, developed by Thomason (Random Graphs 1985) and Chung, Graham, and Wilson (Combinatorica 1989), is a fundamental tool in combinatorics. For a fixed graph H, it states that the number of copies of H in a pseudorandom graph G is similar to the number of copies of H in a purely random graph with the same edge density as G. However, this lemma is only non-trivial when G is a dense graph. In this work, we prove a graph counting lemma that is also effective when G is sparse. Moreover, our lemma is well-suited for density increment arguments in additive number theory. As an immediate application, we obtain a strong bound for the Turán problem in abelian Cayley sum graphs: let Γ be a finite abelian group with odd order. If a Cayley sum graph on Γ does not contain any r-elique as a sub graph, it must have at most 2−Ωr(log1/16|Γ|)⋅|Γ|2 edges. These results hinge on the technology developed by Kelley and Meka and the follow-up work by Kelley, Lovett, and Meka (STOC 2024).
more »
« less
Effective Counting in Sphere Packings
Given a Zariski-dense, discrete group, Γ, of isometries acting on (n + 1)- dimensional hyperbolic space, we use spectral methods to obtain a sharp asymptotic formula for the growth rate of certain Γ-orbits. In particular, this allows us to obtain a best-known effective error rate for the Apollonian and (more generally) Kleinian sphere packing counting problems, that is, counting the number of spheres in such with radius bounded by a growing parameter. Our method extends the method of Kontorovich [Kon09], which was itself an extension of the orbit counting method of Lax-Phillips [LP82], in two ways. First, we remove a compactness condition on the discrete subgroups considered via a technical cut- off and smoothing operation. Second, we develop a coordinate system which naturally corresponds to the inversive geometry underlying the sphere counting problem, and give structure theorems on the arising Casimir operator and Haar measure in these coordinates.
more »
« less
- Award ID(s):
- 2302641
- PAR ID:
- 10627071
- Publisher / Repository:
- Association for Mathematical Research
- Date Published:
- Journal Name:
- Journal of the Association for Mathematical Research
- Volume:
- 2
- Issue:
- 1
- ISSN:
- 2998-4114
- Page Range / eLocation ID:
- 15 to 52
- Subject(s) / Keyword(s):
- Orbital counting, Spectral theory, Automorphic representations
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We introduce Tiered Sampling , a novel technique for estimating the count of sparse motifs in massive graphs whose edges are observed in a stream. Our technique requires only a single pass on the data and uses a memory of fixed size M , which can be magnitudes smaller than the number of edges. Our methods address the challenging task of counting sparse motifs—sub-graph patterns—that have a low probability of appearing in a sample of M edges in the graph, which is the maximum amount of data available to the algorithms in each step. To obtain an unbiased and low variance estimate of the count, we partition the available memory into tiers (layers) of reservoir samples. While the base layer is a standard reservoir sample of edges, other layers are reservoir samples of sub-structures of the desired motif. By storing more frequent sub-structures of the motif, we increase the probability of detecting an occurrence of the sparse motif we are counting, thus decreasing the variance and error of the estimate. While we focus on the designing and analysis of algorithms for counting 4-cliques, we present a method which allows generalizing Tiered Sampling to obtain high-quality estimates for the number of occurrence of any sub-graph of interest, while reducing the analysis effort due to specific properties of the pattern of interest. We present a complete analytical analysis and extensive experimental evaluation of our proposed method using both synthetic and real-world data. Our results demonstrate the advantage of our method in obtaining high-quality approximations for the number of 4 and 5-cliques for large graphs using a very limited amount of memory, significantly outperforming the single edge sample approach for counting sparse motifs in large scale graphs.more » « less
-
In this paper, we consider networks of deterministic spiking neurons, firing synchronously at discrete times. We consider the problem of translating temporal information into spatial information in such networks, an important task that is carried out by actual brains. Specifically, we define two problems:“First Consecutive Spikes Counting” and “Total Spikes Counting”, which model temporal-coding and rate-coding aspects of temporal-to-spatial translation respectively. Assuming an upper bound of T on the length of the temporal input signal, we design two networks that solve two problems, each using O(logT) neurons and terminating in time T+ 1. We also prove that these bounds are tight.more » « less
-
null (Ed.)In this paper, we consider networks of deterministic spiking neurons, firing synchronously at discrete times. We consider the problem of translating temporal information into spatial information in such networks, an important task that is carried out by actual brains. Specifically, we define two problems: "First Consecutive Spikes Counting" and "Total Spikes Counting", which model temporal-coding and rate-coding aspects of temporal-to-spatial translation respectively. Assuming an upper bound of T on the length of the temporal input signal, we design two networks that solve two problems, each using O(log T) neurons and terminating in time T+1. We also prove that these bounds are tight.more » « less
-
We study the asymptotic behavior of the counting function of negative eigenvalues of Schrödinger operators with real valued potentials which decay at infinity on asymptotically hyperbolic manifolds. We establish conditions on the rate of decay of the potential that determine if there are finitely or infinitely many negative eigenvalues. In the latter case, they may only accumulate at zero and we obtain the asymptotic behavior of the counting function of eigenvalues in an interval(-\infty, -E)asE\rightarrow 0.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.56994/JAMR.002.001.002
