RemarkRemark: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Critical-window gap and vanishing epsilon in the authors’ method

PDF p. 38: Section 7, opening paragraph

Statement

Assume countable choice. Write $G (n, p)$ for the simple graph on $n$ labelled vertices whose possible edges are independently present with probability $p$ . A graph is globally synchronizing when, for the homogeneous Kuramoto system in the rotating frame, a uniformly chosen initial phase state converges to a fully synchronized state with probability one. An event holds with high probability when its probability tends to one as $n \to \infty$ .

There is a positive sequence $ε_{n} \to 0$ for which $c_{n} = ε_{n} \log n \to + \infty$ and $G (n, (\log n + c_{n}) / n)$ is globally synchronizing with high probability. This is an existence statement; it supplies no convergence rate and does not establish synchronization for every sequence $c_{n} \to + \infty$ .

The authors identify closing the gap between connectivity and synchronization at $p n = \log n + c_{n}$ with $c_{n} ≫ 1$ as a natural challenge. Their theorem uses $c_{n} = ε \log n$ for fixed $ε > 0$ . They say that a careful look at their computations allows $ε$ to tend to zero, but they establish no convergence rate and say that this would not be sharp. Here $c_{n} ≫ 1$ means $c_{n} \to + \infty$ .

Statement references

Erdős–Rényi random graph and high probability

Globally synchronizing graph — Definition 1.1

Asymptotic quantifiers and uniform parameter ranges

The Axiom of Countable Choice (AC_ω)

Connected graphs and connected components defined by the existence of vertex paths

The natural logarithm as the inverse of the exponential function

Facts & Assumptions

[F1]

Under countable choice, for every fixed $ε > 0$ and every admissible sequence $p (n) \geq (1 + ε) \log n / n$ eventually, $G (n, p (n))$ is globally synchronizing with high probability (Erdős–Rényi global synchronization — Theorem 1.2).

[F2]

If $p_{n} = (\log n + c_{n}) / n \in [0, 1]$ eventually and $c_{n} \to + \infty$ , then $G (n, p_{n})$ is connected with high probability (Connectivity in the logarithmic random-graph window). Connectedness has the path-based meaning of Connected graphs and connected components defined by the existence of vertex paths.

[F3]

The graph law, global-synchrony convention and high-probability limit are those specified in the Statement (Erdős–Rényi random graph and high probability, Globally synchronizing graph — Definition 1.1, Asymptotic quantifiers and uniform parameter ranges).

[F4]

Countable choice permits simultaneous selection of one sufficiently large integer from each of the countably many nonempty sets of valid cutoffs (The Axiom of Countable Choice (AC_ω)).

[F5]

The symbol $\log$ denotes the natural logarithm, the inverse of the real exponential on $(0, \infty)$ (The natural logarithm as the inverse of the exponential function).

[F6]

The natural logarithm is strictly increasing on $(0, \infty)$ , maps this interval onto $R$ , and satisfies $\log 1 = 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F7]

One has $\log n / n \to 0$ as $n \to \infty$ , by the logarithm growth theorem with exponent $1$ (The logarithm grows more slowly than every positive real power).

Proof

Given: Countable choice and the fixed- $ε$ theorem in [F1].

Goal: Construct the sequence in the Statement and identify the scope of the connectivity comparison.

1.1F1F3F4F6F7choose

For each positive integer $k$ , [F6] gives $\log n \geq 0$ for $n \geq 1$ , and [F7] gives $(1 + 1 / k) \log n / n \to 0$ ; hence these quantities belong to $[0, 1]$ eventually. Put $p_{n, k} = (1 + 1 / k) \log n / n$ for all sufficiently large $n$ , and choose any values in $[0, 1]$ at earlier indices. By [F1], the probability that $G (n, p_{n, k})$ is not globally synchronizing tends to zero. Thus there is a cutoff $M_{k}$ beyond which this probability is at most $1 / k$ and $p_{n, k} \in [0, 1]$ . By [F4], choose such cutoffs for all $k$ . For each $k$ , the range assertion in [F6] supplies a real $x_{k} > 0$ with $\log x_{k} = k^{2}$ , and monotonicity gives $\log n \geq k^{2}$ for every integer $n \geq x_{k}$ . Thus we can choose strictly increasing integers $N_{k} \geq M_{k}$ with $N_{k} \geq k$ and $\log N_{k} \geq k^{2}$ .

2.1F2F3F6step 1.1algebra∎

For $N_{k} \leq n < N_{k + 1}$ set $ε_{n} = 1 / k$ ; define the finitely many earlier terms to be any positive values giving admissible probabilities. Since $N_{k}$ is strictly increasing and unbounded, the corresponding $k$ tends to infinity with $n$ . Therefore $ε_{n} \to 0$ , while monotonicity in [F6] gives $ε_{n} \log n \geq (\log N_{k}) / k \geq k$ on the $k$ th block. On that block the failure probability is at most $1 / k$ , so it tends to zero. This proves the asserted synchronization and $c_{n} \to + \infty$ ; [F2] also gives connectivity with high probability along this particular sequence. The choices of cutoffs give no explicit rate and make no assertion for an arbitrary diverging $c_{n}$ .

Source notes

The final paragraph of the Statement attributes the authors’ discussion to the cited article. The proof above is a diagonal consequence of the completed fixed- $ε$ theorem; it does not reconstruct or verify the authors’ proposed use of their computations. Connectivity is used only for comparison, not as a premise implying synchronization.

Depends on

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing · PDF p. 38, Section 7, opening paragraph