Alec Kriebel

Sharp modulus range for triangle counts in dense random graphs

Read the paper (PDF) · Download PDF · Supporting ZIP · Zenodo record

Plain-English explanation · Read on this page · Collaboration


Abstract

Fix 0 < p < 1, and let Tn count each triangle once in G(n,p). For every positive integer sequence qn, we give the explicit deduction

max0 ≤ a < qₙ |qₙ P(Tₙ ≡ a mod qₙ) − 1| → 0 ⇔ qₙ = o(n²).

Sufficiency follows from the quantitative local limit theorem of Sah and Sawhney, concentration, and finite-window summation. Necessity follows from an elementary edge-projection central limit theorem and a modular Fourier coefficient. This covers arbitrary, possibly oscillating or composite, modulus sequences. We also reconcile density and Gaussian unit-cell conventions. The result is a credited corollary of earlier local limit work, addressing the sharp range in Scott’s 2009 report of joint work with Tateno. No novelty, historical firstness, or new local limit theorem is claimed.

The idea in plain English

Make a random graph by deciding independently whether to draw each possible edge, then count its triangles. Remainders after division by q become equally likely when q grows more slowly than the scale of the triangle count’s fluctuations. In this model that scale is n².

The precise result

With fixed edge probability p ∈ (0, 1), the probability of each remainder, divided by the ideal probability 1/qn, tends uniformly to 1 exactly when qn/n² tends to zero.

Why the scale is n²

A quantitative local limit theorem approximates integer triangle counts by a Gaussian density. Concentration controls the distant tails, and summing every qn-th count gives uniform residues on a mesh finer than the standard deviation.

If the modulus reaches the fluctuation scale along a subsequence, one nonzero Fourier mode keeps a positive limiting magnitude. Uniform residues would force that mode to disappear.

Scope

The edge probability is fixed as the graph grows. The count is of unordered triangles, and the error is relative to the uniform probability. Bounded, composite and oscillating sequences of positive integer moduli are covered.

Background and prior work

The sharp scale appears in Scott’s report of joint work with Tateno. The note makes the deduction explicit from the quantitative theorem of Sah and Sawhney and discusses the earlier modular bounds of Gilmer and Kopparty.

Status and AI use

Unrefereed preprint. AI tools assisted substantially in developing, writing and checking the work. Independent human review is welcome.

Read the paper

Open the published PDF · Download PDF · Original PDF on Zenodo

Supporting materials

Download Triangle_Modular_Threshold_Verification_v1.0.zip · Original Triangle_Modular_Threshold_Verification_v1.0.zip on Zenodo

Collaborate on this result

I welcome an independent check of the uniform error estimate and its treatment of slowly growing or oscillating moduli.

Authorship and responsibilities would be discussed in relation to substantive contributions. Contact Alec.

Cite this paper

Kriebel, Alec (2026). Sharp modulus range for triangle counts in dense random graphs. Version 1.0. Zenodo. 10.5281/zenodo.23443230.

Download BibTeX

Licensing

The deposited work is available under Creative Commons Attribution 4.0.