Three-fault re-rooting in dense Gaussian networks: an obstructed fault set for every diameter, and the census of obstructed triples

Abstract

The dense Gaussian network Gₖ is the circulant graph C_N(k,k+1) on N=2k²+2k+1 nodes, of degree four and diameter k. Albader, Al-Mulla and Hassan (arXiv:2606.16954) make one-to-all broadcasting tolerate a set F of faulty nodes by re-rooting it at a node whose hop distance from every faulty node is the diameter k; writing Bₖ for the set of nodes at distance k from 0, such a node exists exactly when bigcap_(f ∈ F)(f+Bₖ) ≠ emptyset. They prove that every one- or two-fault set admits a re-rooted source, for every k, exhibit one three-fault set in G₃ that does not, and leave the three-fault case there. We show that for every k ≥ 3 the network Gₖ contains a three-fault set with no re-rooted source. For k ≥ 16 this is a counting argument valid in any circulant: every re-rootable pair (a,b) — one for which {0,a,b} is re-rootable — is the image of a triple of boundary nodes under (v,p,q) ↦ (v-p,v-q), so |Bₖ|³+3N<N² forces an obstructed pair, and the input |Bₖ| ≤ 4k+2 comes from a two-sided lattice description of hop distance in Gₖ. For 3 ≤ k ≤ 15 the explicit set {0, k+3, 3k+3} is obstructed; enumeration extends this rule to k ≤ 60 and shows that for k ≤ 30 it is the lexicographically first obstructed triple, but a proof for all k is not given. We also determine the exact number T₃(k) of obstructed three-fault sets for k=3,…,10 (50, 738, 4636, 18700, 57630, 148190, 334488, 684216) and tabulate the enumerated values to k=30, where the obstructed triples become the majority at k=14. Every theorem is verified in Lean 4 against Mathlib: the counting theorem, the lattice characterisation and the case k ≥ 16 are checked by the kernel alone, the finite parts by compiled evaluation.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   9e6b51a26ca05c44d36da0c90fd4b6d05466208514e537baeb53a50776eae16f