Repair depth of multi-orientation edge-minimum broadcast repair in dense Eisenstein–Jacobi networks: depth t+1 suffices for two faults at every diameter 4 ≤ t ≤ 19

Abstract

The dense Eisenstein–Jacobi network Hₜ is the Cayley graph of ℤ[ω]/(α), α=(t+1)+tω, on the six units; it has N=3t²+3t+1 vertices and diameter t. Albader (arXiv:2606.19834) repairs a source-rooted broadcast tree of Hₜ after the failure of at most two vertices by choosing one of fifteen coordinate-reduction orientations, deleting the faults, and reconnecting the surviving components with the minimum number c-1 of external edges (EJ-MOEM). He proves that a valid repair of depth at most t+2 always exists, observes in an exhaustive table that depth t+1 sufficed for every one- and two-fault placement at t=2,…,12,14,16,18 except at t=3, and asks whether depth t+1 is universally sufficient for t ≥ 4. We answer the question for every diameter 4 ≤ t ≤ 19: for each of the 2,871,160 fault sets F with |F| ≤ 2 some orientation admits a valid non-redundant repair of depth at most t+1 (the diameters 13,15,17,19 lie outside the source's table), and for 4 ≤ t ≤ 18 the bound is attained by an explicit two-fault placement that admits no valid repair of depth ≤ t in any orientation, the minimum being taken over all valid repairs and not over the output of one algorithm. At t=3 the exceptional placements are exactly the six pairs of adjacent vertices at distance one from the source, with repair depth exactly 5=t+2; every other placement has depth at most 4. Restricting to star repairs, in which every repair edge leaves the source component, the optimum is exactly 2t-1 for 4 ≤ t ≤ 8, so at those diameters chaining detached components is necessary and its absence costs t-2 units of depth. Two errata in the source's algebra are recorded: the displayed root of unity is a cube root where the model needs a sixth root, and the printed vertex label is not well defined on ℤ[ω]/(α). Every finite statement is certified by compiled evaluation of a certificate checker inside Lean 4; the errata rest on identities the Lean kernel proves for every t.

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

   06153deeed2c28adac7b5037c0fd3661602126fd1d4ccb6952b1b78d44c59b4a