Local Fault Repair of Perfect Resource Placements in Eisenstein–Jacobi Networks Bader A. Albader
arXiv:2606.17288v1 [cs.DC] 15 Jun 2026
Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract Perfect resource placements in dense Eisenstein–Jacobi networks partition the network into hexagonal radius-t service cells. The fault-free placement problem is already classified; this paper studies the complementary post-deployment problem of locally repairing such placements after resource failures. For the dense Eisenstein–Jacobi family generated by α = n + (n − 1)ω, with t = n − 1, we first prove failure-cell locality and candidate locality. For one failed resource, we prove that one nonfailed replacement cannot cover the failed hexagon and that two replacements always suffice; hence ρEJ (t) = 2 for every t ≥ 1. Among all minimum-size one-fault repairs, we prove the sharp minimum-overlap formula ΩEJ (t) = t2 . The lower bound follows from the three-strip geometry of Eisenstein–Jacobi balls: every two-ball cover of a failed hexagonal cell contains a forced t × t axial interface region. We then extend the framework beyond one fault. For two failed resources, independent repair gives a universal fourreplacement upper bound, but unlike the Gaussian case the EJ geometry is not always additive: we give explicit three-replacement constructions for two infinite neighboring displacement families and prove algebraic three-strip constructions for the infinite non-additive neighboring families. For additive neighboring pairs, we prove two algebraic lower-bound mechanisms: an endpoint-rigidity theorem for pairs with separated opposite axial endpoints, and a diagonal-corridor theorem for the remaining family D = ±(g1 + g2 ). Thus the closed-form two-fault section separates the non-additive neighboring families from the additive mechanisms without leaving the diagonal corridor as an open case. For q failed resources, independent canonical repair gives a universal 2q upper bound, and this bound is exact whenever failed cells are separated by more than 4t in Eisenstein–Jacobi distance. We also identify and prove infinite dense four-fault and six-fault cluster families: the four-fault cluster has exact repair number four rather than eight, and the six-fault cluster has exact repair number five rather than twelve, showing strong multi-fault subadditivity. For arbitrary multi-fault repairs, we prove an exact inclusion–exclusion identity for repeated coverage inside the failed region and its low-multiplicity specializations. A second exact optimization audit over 19,400 multi-fault instances for 2 ≤ t ≤ 12 and 3 ≤ q ≤ 6 confirms widespread subadditivity, including q = 6 instances with saving seven relative to independent repair. The results show that Eisenstein–Jacobi local repair is not a direct copy of the Gaussian case: the one-fault overlap is quadratic, neighboring two-fault repair can
1
drop from four to three, and dense clustered repairs can reuse replacement balls across several failed hexagonal cells.
Keywords: Eisenstein–Jacobi networks; resource placement; perfect domination; local repair; fault tolerance; hexagonal networks; interconnection networks
1
Introduction
Resource placement is a basic abstraction for allocating servers, controllers, memory modules, I/O nodes, or monitoring nodes in a large interconnection network. A radius-t placement is perfect when every network vertex is within distance t of exactly one resource. Equivalently, the radius-t balls centered at the resource nodes partition the network. Perfect resource placement in Gaussian and Eisenstein–Jacobi interconnection networks was classified by Flahive and Bose [1]. That result is fault-free: it determines when a perfect placement exists and describes the corresponding lattice of resource nodes. The present paper starts after deployment. It assumes that a classified perfect placement is already active and asks what must be done after a resource node fails. The operational objective is local repair. If a resource r fails, the vertices outside its former service cell remain served by the surviving resources. Thus the post-fault task is not to recompute a new global perfect placement, but to activate a small set of nearby replacement resources that covers the failed cell. This creates a finite geometric optimization problem: minimize the number of replacements and, among minimum-size repairs, minimize the number of vertices that are served more than once inside the failed cell. From a systems perspective, constant-size repair rules are useful because a controller does not need to solve a global placement problem after a resource fault. Once the dense EJ placement is deployed, the controller needs only the failed resource coordinate, the radius t, and the local displacement class of any clustered fault pattern. The replacement centers are then obtained from closed-form coordinate rules or from a small local pattern library. This supports fast reconfiguration in large interconnection networks where global remapping would be expensive, disruptive, or undesirable during transient resource, controller, memorymodule, or service-node failures. This paper develops the Eisenstein–Jacobi analogue of the Gaussian local-repair framework. The separation is necessary because the two geometries have different extremal structure. In the Gaussian case, Lee balls become parity-constrained squares after a coordinate rotation, and the sharp one-fault overlap is linear in t. In the Eisenstein–Jacobi case, balls are discrete hexagons described by three axial strip constraints, and the sharp one-fault overlap is quadratic. Fault tolerance in graph-based networks has also been studied through complementary robustness parameters, including fault-tolerant metric dimension [10], diagnosability of interconnection networks [11], and fault-tolerant domination variants such as power domination [12]. The broader domination literature contains foundational and survey work on perfect and independent domination [7, 8, 9]. Resource placement in tori and related interconnection networks was studied earlier in [4, 5, 6]. Eisenstein–Jacobi and hexagonal network models have been developed in [3, 2, 13, 14]. The present paper is different in focus: the original 2
resource set is already a perfect dominating set, and the objective is to determine the exact local replacement cost after a deployed resource fails. The contributions are as follows. • We formulate local fault repair for perfect Eisenstein–Jacobi resource placements as a post-deployment domination-recovery problem. • We prove failure-cell locality and candidate locality: after one resource fails, only its former hexagonal service cell can become uncovered, and replacements farther than 2t from the failed resource cannot contribute. • We prove the exact one-fault replacement number ρEJ (t) = 2 for all t ≥ 1. • We prove the exact one-fault minimum-overlap formula ΩEJ (t) = t2 among minimumsize repairs. • We identify a canonical family of 3t two-center repairs attaining the optimum overlap, and we verify by exhaustive enumeration that these are exactly the optimal pairs for 1 ≤ t ≤ 20. • We prove a universal four-replacement upper bound for two failed resources and show algebraically that dense EJ repair is non-additive for specific neighboring displacement families: three replacements are both sufficient and necessary for those infinite families. • We add endpoint-rigidity and diagonal-corridor theorems for additive two-fault pairs. Together these close the symbolic additive mechanisms needed after the explicit nonadditive families are separated. • We prove a universal 2q upper bound for q failed resources by independent canonical repair and prove exact 2q additivity for pairwise 4t-separated failed cells. • We identify dense four-fault and six-fault cluster families with exact repair numbers four and five, respectively, giving proved savings of four and seven replacements relative to independent repair. • We prove an exact multi-failure overlap identity using replacement multiplicities inside the failed region, together with explicit low-multiplicity specializations such as P2 − P3 + P 4 . • We include reproducible one-fault and multi-fault audits analogous to the Gaussian study, recomputing coverage and overlap directly from lattice geometry. Table 1 summarizes the formal results.
3
Table 1: Main results and proof locations. Setting
Result
Proof method
One failed resource
Only the failed hexagonal cell can become uncovered; candidates outside radius 2t are irrelevant ρEJ (t) = 2 for all t ≥ 1
Perfectness and triangle inequality
One failed resource One failed resource, minimum overlap Canonical one-fault repairs
ΩEJ (t) = t2
Two failed resources
ρEJ (t, F ) ≤ 4 always; non-additive K = 3 neighboring families exist 78 non-additive and 754 additive neighboring cases for 2 ≤ t ≤ 20 (q) ρEJ (t, F ) ≤ 2q
(2)
Two-fault validation q failed resources
(q)
Pairwise separated failures General multi-fault overlap
2
3t canonical optimum-overlap pairs
ρEJ (t, F ) = 2q if all failed centers are more than P 4t apart O(R) = j≥2 (−1)j Pj (R)
Six extreme vertices and explicit two-center cover Three-strip slice lower bound and tight axial-interface construction Three axial orientations and t interface positions per orientation; exact audit for t ≤ 20 Independent repair upper bound and explicit three-ball constructions Bounded exact optimizer audit; not used as a universal theorem Independent translated canonical repairs Candidate-intersection locality plus one-cell lower bound Vertexwise binomial inclusion– exclusion over multiplicities
Eisenstein–Jacobi Preliminaries
Let
√ −1 + i 3 . ω= 2
(1)
Z[ω] = {x + yω : x, y ∈ Z}.
(2)
The Eisenstein integer lattice is
We use axial coordinates and identify x + yω with the pair (x, y). Two vertices are adjacent when their difference is one of the six unit Eisenstein directions ±(1, 0),
±(0, 1),
±(1, −1).
(3)
The graph distance from the origin is dEJ ((0, 0), (x, y)) = max{|x|, |y|, |x + y|}.
(4)
dEJ ((a, b), (x, y)) = max{|x − a|, |y − b|, |x + y − a − b|}.
(5)
By translation,
The radius-t ball centered at c is Bt (c) = {u : dEJ (u, c) ≤ t}.
(6)
The central ball is the discrete hexagon Ht = Bt (0) = {(x, y) : |x| ≤ t, |y| ≤ t, |x + y| ≤ t}. 4
(7)
It has |Bt (0)| = 3t2 + 3t + 1
(8)
vertices. Figure 1 shows the three-strip description of this hexagonal ball and labels the six extreme vertices used later in the repair lower bounds.
Figure 1: EJ radius-t ball as the intersection of three axial strips for t = 3. The discrete hexagon Bt (0) is defined by |x| ≤ t, |y| ≤ t, and |x+y| ≤ t; its six extreme vertices determine the ball center and drive the one-fault impossibility proof. For the dense Eisenstein–Jacobi family generated by α = n + (n − 1)ω,
t = n − 1,
(9)
N = 3n2 − 3n + 1 = 3t2 + 3t + 1.
(10)
the network order is The integer label associated with the axial coordinate (x, y) is ϕ(x + yω) ≡ (n − 1)x − ny
(mod N ).
(11)
The labeling is useful for implementation and for matching numbered EJ-network diagrams. The proofs below are stated in axial coordinates, where the three-strip structure of the balls is explicit. Definition 1 (Perfect EJ t-placement). A resource set S is a perfect EJ t-placement if every vertex of the network is within Eisenstein–Jacobi distance t of exactly one resource node in S. Theorem 1 (EJ resource-placement classification [1]). Eisenstein–Jacobi networks admit perfect t-dominating placements exactly in the canonical divisibility cases. In the dense case generated by α = n + (n − 1)ω, the corresponding placement is a translate of the ideal generated by α, with service radius t = n − 1.
5
Proposition 1 (Associate and conjugate generator symmetry). Let α0 = n + (n − 1)ω.
(12)
Every dense EJ generator obtained from α0 by multiplication by an Eisenstein unit in U = {1, −1, ω, −ω, ω 2 , −ω 2 }
(13)
or by first conjugating and then multiplying by a unit has the same local-repair parameters as α0 . In particular, the replacement numbers, overlap values, and dense-cluster identities proved below are invariant under all associate and conjugate companion generator choices. Proof. Write an Eisenstein–Jacobi element as a coordinate pair (a, b) meaning a + bω. Multiplication by the six units acts as unit u 1 −1 ω −ω ω2 −ω 2
coordinate image of (a, b) for u(a + bω) (a, b) (−a, −b) (−b, a − b) (b, −a + b) (−a + b, −a) (a − b, a)
Conjugation sends (a, b) to (a − b, −b) because ω = ω 2 = −1 − ω. Applying these maps to α0 = (n, n − 1) gives the associate orbit (n, n − 1), (−n, 1 − n), (1 − n, 1), (n − 1, −1), (−1, −n), (1, n),
(14)
and applying them to the conjugate generator α0 = (1, 1 − n) gives (1, 1 − n), (−1, n − 1), (n − 1, n), (1 − n, −n), (−n, −1), (n, 1).
(15)
These maps are automorphisms of the triangular lattice: they permute the six unit directions ±(1, 0), ±(0, 1), and ±(1, −1) and therefore preserve the distance formula (4). They map radius-t EJ balls to radius-t EJ balls, map perfect placement cells to congruent perfect placement cells, and preserve coverage multiplicities. Since the local repair model is defined only through these metric balls and their incidences, every local-repair statement transfers unchanged to all listed associate or conjugate dense generators.
3
Fault-Recovery Model
Let S be a perfect EJ t-placement and let r ∈ S fail. A repair set R ⊆ V \ S is valid if [ Bt (r) ⊆ Bt (q). (16) q∈R
6
The one-fault repair number is ρEJ (t) = min{|R| : R is a valid repair for r}.
(17)
By translation invariance, ρEJ (t) does not depend on r. The translated canonical repair algorithm places one two-center repair pair at the resource coordinate r: R∗ (r) = {r − (1, 0), r + t(1, 0)}. (18) By the two-center cover lemma proved below, R∗ (r) is a valid repair for every r. Among minimum-size repair sets, we also measure the unavoidable repeated coverage inside the failed cell. For a two-replacement repair R = {q1 , q2 }, define ov(R) = |Bt (r) ∩ Bt (q1 ) ∩ Bt (q2 )|.
(19)
The minimum-overlap value is ΩEJ (t) = min{ov(R) : |R| = ρEJ (t), R repairs r}.
4
(20)
Locality Theorems
The locality argument is independent of the detailed shape of the EJ ball. It uses only perfectness of the original placement and the metric triangle inequality. Theorem 2 (Failure-cell locality). Let S be a perfect EJ t-placement and let r ∈ S fail. Then the only vertices that can become uncovered are the vertices in Bt (r). Proof. Since S is a perfect t-placement, every vertex was covered by exactly one resource. If a vertex u is not in Bt (r), then r was not the resource covering u. Therefore the unique resource that covered u remains active after r is removed. Only vertices originally covered by r, namely the vertices of Bt (r), can become uncovered. Theorem 3 (Candidate locality). If a candidate replacement q satisfies dEJ (q, r) > 2t, then Bt (q) ∩ Bt (r) = ∅. Hence q cannot contribute to repairing the failed cell. Proof. If u ∈ Bt (q) ∩ Bt (r), then dEJ (q, r) ≤ dEJ (q, u) + dEJ (u, r) ≤ 2t,
(21)
contradicting dEJ (q, r) > 2t.
5
Exact One-Fault Repair Number
By translation invariance, assume that the failed resource is the origin. Thus the failed cell is the central hexagon Ht = Bt (0).
7
Figure 2: The small case t = 1. Unlike the Gaussian case, EJ has no exceptional repair number: two replacement balls cover the seven-vertex failed hexagon, and their overlap contains exactly one vertex. Lemma 1 (A single nonfailed replacement is impossible). For every t ≥ 1, no vertex q ̸= (0, 0) satisfies Bt (0) ⊆ Bt (q). (22) Proof. The two balls have the same finite cardinality. Therefore containment would imply Bt (0) = Bt (q). The center of an EJ ball is determined uniquely by its six extreme vertices (t, 0),
(0, t),
(−t, t),
(−t, 0),
(0, −t),
(t, −t).
(23)
Equivalently, every pair of opposite extreme vertices has midpoint equal to the center. To see this directly, the opposite pair (t, 0) and (−t, 0) forces the x-midline of the ball to be x = 0; the opposite pair (0, t) and (0, −t) forces the y-midline to be y = 0; and the pair (−t, t) and (t, −t) forces the (x + y)-midline to be x + y = 0. These three midlines meet only at (0, 0). Equality of the two balls therefore forces q = (0, 0), which is unavailable because the resource at the origin has failed. Lemma 2 (Two-center EJ cover). For every t ≥ 1, Bt (0) ⊆ Bt ((−1, 0)) ∪ Bt ((t, 0)).
(24)
Proof. Let (x, y) ∈ Bt (0), so |x| ≤ t,
|y| ≤ t,
|x + y| ≤ t.
(25)
|y| ≤ t,
|x + y + 1| ≤ t,
(26)
If x ≤ t − 1 and x + y ≤ t − 1, then |x + 1| ≤ t,
8
because x ≥ −t and x + y ≥ −t. Thus (x, y) ∈ Bt ((−1, 0)). It remains to consider vertices for which x = t or x + y = t. If x = t, then (25) gives −t ≤ y ≤ 0. Hence |x − t| = 0,
|y| ≤ t,
|x + y − t| = |y| ≤ t,
(27)
so (x, y) ∈ Bt ((t, 0)). If x + y = t, then (25) gives 0 ≤ x ≤ t, and therefore |x − t| ≤ t,
|y| = |t − x| ≤ t,
|x + y − t| = 0.
(28)
Thus (x, y) ∈ Bt ((t, 0)). The cases exhaust Bt (0).
Figure 3: Explicit two-center one-fault repair for t = 4. Blue vertices are covered only by the left replacement, orange vertices only by the right replacement, and yellow vertices form the overlap region Qt . Example 1 (Worked t = 4 one-fault repair). In Fig. 3, the failed cell is B4 (0) and the repair centers are (−1, 0) and (4, 0). The two balls split the hexagon along the axial interface x = 0 and x + y = 0; their common part is the highlighted region Q4 , containing 42 = 16 vertices. This example is the concrete instance of Lemma 2 and of the sharp overlap formula proved later. Lemma 3 (Explicit t = 1 verification). For t = 1, the failed EJ cell has seven vertices, two replacements are sufficient, and one replacement is impossible. Hence the general formula ρEJ (1) = 2 has no small-radius exception.
9
Figure 4: Three axial orientations of the canonical optimum repair family. For each of the three EJ axes and each interface position a = 1, . . . , t, the pair {−aei , (t + 1 − a)ei } covers the failed cell and attains overlap t2 . Proof. The failed cell is B1 (0) = {(0, 0), (1, 0), (0, 1), (−1, 1), (−1, 0), (0, −1), (1, −1)}.
(29)
The pair {(−1, 0), (1, 0)} is the specialization of Lemma 2 and covers all seven vertices. Lemma 1 rules out one replacement. Therefore ρEJ (1) = 2. Example 2 (Worked t = 1 repair). For t = 1, the repair pair {(−1, 0), (1, 0)} covers the seven vertices of B1 (0) shown in Fig. 2. The only repeated vertex is the origin, so the overlap value is 1 = t2 . Thus the small case agrees with both main one-fault formulas, ρEJ (1) = 2 and ΩEJ (1) = 1. Theorem 4 (Exact one-fault EJ repair number). For every t ≥ 1, ρEJ (t) = 2.
(30)
Proof. The previous impossibility lemma rules out one replacement. The two-center cover in Lemma 2 gives a valid repair with two replacements.
6
Canonical Optimal Repair Family
The explicit pair in Lemma 2 is one member of a larger axial family. Let the three unoriented EJ axes be represented by e1 = (1, 0),
e2 = (0, 1),
e3 = (1, −1).
(31)
For each a ∈ {1, . . . , t} and each axis direction ei , define Ri,a = {−aei , (t + 1 − a)ei }.
(32)
There are 3t such unordered pairs. Figure 4 illustrates the three axial orientations and the way the interface position changes with a. Proposition 2 (Canonical optimal pairs). Every pair Ri,a in (32) covers Bt (0) and has overlap exactly t2 inside Bt (0). 10
Proof. It suffices to prove the claim for e1 = (1, 0), since the EJ hexagon is invariant under the dihedral symmetries permuting the three axes. Thus consider R1,a = {(−a, 0), (t + 1 − a, 0)},
1 ≤ a ≤ t.
(33)
The same argument as Lemma 2 splits the failed hexagon between the two supporting boundaries x = t − a + 1 and x + y = t − a + 1. The first ball covers the vertices satisfying x ≤ t − a,
x + y ≤ t − a,
(34)
and the second ball covers all remaining failed-cell vertices with x ≥ t−a+1 or x+y ≥ t−a+1. Therefore the union covers Bt (0). The common part inside the failed cell is Qt,a = {(x, y) : 1 − a ≤ x ≤ t − a, −x ≤ y ≤ t − 1 − x}.
(35)
For each of the t admissible x-values, the interval for y contains exactly t lattice points. Thus |Qt,a | = t2 . Symmetry gives the same result for e2 and e3 .
7
Exact Minimum Overlap for One Fault
The repair number alone does not measure efficiency. A two-center repair may cover the failed hexagon, but it necessarily creates repeated coverage inside the failed cell. We now determine the minimum possible repeated coverage. For the explicit repair R∗ = {(−1, 0), (t, 0)}, the overlap inside Bt (0) is the axial rectangle Qt = {(x, y) : 0 ≤ x ≤ t − 1, −x ≤ y ≤ t − 1 − x}.
(36)
For each x ∈ {0, 1, . . . , t − 1} there are exactly t admissible values of y, so |Qt | = t2 . Figure 5 shows these t parallel slices explicitly; it is the geometric picture behind the lower-bound proof.
11
Figure 5: Forced axial-interface overlap. Any two-ball cover has a transition region containing t disjoint axial slices, each with t vertices. This is the geometric source of the sharp quadratic overlap ΩEJ (t) = t2 . Lemma 4 (Overlap attained by the explicit repair). The repair set R∗ = {(−1, 0), (t, 0)}
(37)
|Bt (0) ∩ Bt ((−1, 0)) ∩ Bt ((t, 0))| = t2 .
(38)
has overlap Proof. A vertex (x, y) ∈ Bt (0) lies in both replacement balls if and only if |x + 1| ≤ t, |x − t| ≤ t,
|y| ≤ t, |y| ≤ t,
|x + y + 1| ≤ t, |x + y − t| ≤ t.
(39) (40)
Together with the central inequalities, these conditions reduce to (36). Counting gives t choices of x and t choices of y for each x, hence t2 vertices. Lemma 5 (Forced axial-interface overlap). Let A and B be two nonzero EJ vertices such that Bt (0) ⊆ Bt (A) ∪ Bt (B). (41) Then |Bt (0) ∩ Bt (A) ∩ Bt (B)| ≥ t2 .
(42)
Proof. Write the central hexagon as the intersection of the three strips −t ≤ x ≤ t,
−t ≤ y ≤ t, 12
−t ≤ x + y ≤ t.
(43)
A translated EJ ball is obtained by shifting the same three strips. Hence, on every line parallel to one of the three axial directions, its intersection with that line is an interval of consecutive lattice vertices. Consider the six extreme vertices of Bt (0) in cyclic order, grouped into the three opposite pairs. A translated radius-t hexagon distinct from Bt (0) cannot contain an opposite pair of these extremes: such a pair fixes the corresponding strip midline, and the three opposite pairs together fix the center at the origin. Hence each replacement ball can contain at most one extreme from each opposite pair, and therefore at most three extreme vertices. Since the two replacement balls together cover all six extremes, each ball contains exactly three extremes, one from each opposite pair. The boundary intersection of a translated hexagon with the central hexagon is connected in cyclic order: on each of the six boundary sides, the three strip inequalities defining the translated ball reduce to consecutive integer intervals, and adjacent nonempty side intervals meet only at shared boundary vertices. Thus the split is a complementary 3 + 3 split. By a dihedral symmetry of the EJ hexagon and, if necessary, by interchanging A and B, the unique transition between the two triples may be placed in the canonical sector bounded by the supporting lines x = 0 and x + y = t − 1. Thus only this canonical 3 + 3 transition needs to be analyzed. For i = 0, 1, . . . , t − 1, define the axial slice Li = {(i, y) : −i ≤ y ≤ t − 1 − i}.
(44)
Each Li has exactly t vertices, and the slices are pairwise disjoint. We now spell out the endpoint calculation. For a center C = (c1 , c2 ), the intersection of Bt (C) with the vertical line x = i is the integer interval IC (i) =[c2 − t, c2 + t] ∩ [c1 + c2 − i − t, c1 + c2 − i + t],
(45)
provided |i − c1 | ≤ t, and is empty otherwise. The slice Li itself is the interval Ji = [−i, t − 1 − i].
(46)
We now derive the endpoint ordering explicitly. The normalized split places the lower transition side on the supporting line x = 0 and the upper transition side on x + y = t − 1. Thus, for each 0 ≤ i ≤ t − 1, the lower endpoint ℓi = (i, −i)
(x = i, x + y = 0)
(47)
is the first vertex of the transition slice met from the lower arc, while the upper endpoint ui = (i, t − 1 − i)
(x = i, x + y = t − 1)
(48)
is the last vertex met before the upper arc. In the normalized order, Bt (B) contains the lowerside transition boundary and Bt (A) contains the upper-side transition boundary. Hence −i ∈ IB (i),
t − 1 − i ∈ IA (i). 13
(49)
The remaining endpoint inequalities follow from the shifted strip equations, not from a separate geometric assertion. Write A = (a1 , a2 ) and B = (b1 , b2 ). Since ui ∈ Bt (A), the two interval inequalities in (45) give a2 − t ≤ t − 1 − i ≤ a2 + t,
a1 + a2 − i − t ≤ t − 1 − i ≤ a1 + a2 − i + t.
(50)
In the normalized 3 + 3 transition, the A-side triple occupies the opposite side of the same vertical slice, so the supporting line x = 0 also places the lower endpoint of the slice in the A-side interval. Thus the shifted strips of Bt (A) give the pair of inequalities a2 − t ≤ −i,
a1 + a2 − i − t ≤ −i.
(51)
Equations (50) and (51) say exactly that [−i, t − 1 − i] ⊆ IA (i).
(52)
Similarly, since ℓi ∈ Bt (B) and the opposite transition side is supported by x + y = t − 1, substituting ℓi and ui into the shifted y- and (x + y)-strip inequalities gives b2 − t ≤ −i ≤ b2 + t,
b1 + b2 − i − t ≤ −i ≤ b1 + b2 − i + t,
(53)
b1 + b2 − i + t ≥ t − 1 − i.
(54)
plus the right-endpoint inequalities b2 + t ≥ t − 1 − i, Therefore [−i, t − 1 − i] ⊆ IB (i).
(55)
Since Ji = [−i, t − 1 − i] ⊆ IA (i) ∩ IB (i), every vertex of Li lies in both Bt (A) and Bt (B). Summing over i = 0, . . . , t − 1 gives at least t · t = t2 vertices in the triple overlap. Theorem 5 (Exact minimum overlap). For every t ≥ 1, ΩEJ (t) = t2 .
(56)
Proof. The forced overlap lemma gives the lower bound. The explicit repair R∗ attains t2 . Corollary 1 (Translated overlap lower bound). For every resource center r and every valid two-center repair of Bt (r), ov(R) ≥ t2 . (57) Proof. Translate Proposition 2 by r.
14
8
Two-Fault Repair: Additivity and Non-Additivity
The one-fault theorem immediately gives a four-replacement upper bound for two failed resources. Let F = {r1 , r2 } ⊆ S (58) be the failed pair and let U (F ) = Bt (r1 ) ∪ Bt (r2 ) be the two-cell failed region. A repair set R is valid if [ U (F ) ⊆ Bt (z).
(59)
(60)
z∈R (2)
For a fixed failed pair F , write ρEJ (t, F ) for the minimum number of replacements needed to cover U (F ). Theorem 6 (Two-fault upper bound). For every pair of failed resource centers F = {r1 , r2 }, (2)
ρEJ (t, F ) ≤ 4.
(61)
Proof. For each failed resource ri , choose one translated canonical repair pair from (18); for instance, Ri = {ri − (1, 0), ri + t(1, 0)}. (62) By Corollary 1, Ri covers Bt (ri ). Hence R1 ∪ R2 covers Bt (r1 ) ∪ Bt (r2 ) and uses at most four replacement centers. In the Gaussian local-repair paper, the corresponding two-fault value is always additive for t ≥ 2. The EJ case is different. Neighboring EJ hexagons can share enough boundary structure that one replacement ball can participate in repairing both failed cells, reducing the two-fault repair number from four to three.
Figure 6: Non-additive two-fault repair for the neighboring family D = g2 = (−t, 1) at t = 4. Three replacement balls cover the union of the two failed hexagons, so the repair is strictly better than independent four-ball repair. 15
The dense EJ resource lattice associated with α = (t + 1) + tω is generated in axial coordinates by g1 = (t + 1, t), g2 = (−t, 1). (63) Thus a neighboring displacement can be written as D = mg1 + ng2 .
(64)
By translation, it suffices to take r1 = (0, 0) and r2 = D. Lemma 6 (First non-additive neighboring family). Let t ≥ 2 and let the two failed centers be r1 = (0, 0), r2 = (−t, 1) = g2 . (65) Then the three centers R = {(−t, 0), (1, 0), (−t, 3)}
(66)
cover Bt (r1 ) ∪ Bt (r2 ). By reflection, the displacement (t, −1) = −g2 also has a threereplacement repair. Proof. A vertex z = (x, y) lies in a ball Bt (c1 , c2 ) exactly when |x − c1 | ≤ t,
|y − c2 | ≤ t,
|x + y − c1 − c2 | ≤ t.
(67)
R3 = (−t, 3).
(68)
Put R1 = (−t, 0),
R2 = (1, 0),
We verify the two failed cells separately by explicit strip intervals. If z ∈ Bt (0, 0), then −t ≤ x, y, x + y ≤ t. If x ≤ 0 and x + y ≤ 0, then z ∈ Bt (R1 ). Otherwise x ≥ 1 or x + y ≥ 1. In the first case, the inequalities y ≥ −t and x + y ≥ 1 − t follow from z ∈ Bt (0, 0); in the second case, x ≥ 1 − t follows similarly. Thus in either case z satisfies 1 − t ≤ x ≤ 1 + t,
−t ≤ y ≤ t,
1 − t ≤ x + y ≤ 1 + t,
(69)
1 − 2t ≤ x + y ≤ 1.
(70)
so z ∈ Bt (R2 ). Hence Bt (0, 0) ⊆ Bt (R1 ) ∪ Bt (R2 ). Now let z ∈ Bt (−t, 1). Then −2t ≤ x ≤ 0,
1 − t ≤ y ≤ 1 + t,
If y ≤ t and x + y ≤ 0, then z ∈ Bt (R1 ). Otherwise y = t + 1 or x + y = 1. If y = t + 1, then x + y ≤ 1 gives x ≤ −t, and hence x + y ≥ 1 − t ≥ 3 − 2t for t ≥ 2. If x + y = 1, then y = 1 − x ≥ 1 ≥ 3 − t. In both cases −2t ≤ x ≤ 0,
3 − t ≤ y ≤ 3 + t,
3 − 2t ≤ x + y ≤ 3,
(71)
which is exactly the strip system for Bt (R3 ). Therefore Bt (−t, 1) ⊆ Bt (R1 ) ∪ Bt (R3 ). The two containments prove the claimed three-ball cover. The reflected displacement follows from (x, y) 7→ (−x, −y).
16
Lemma 7 (Second non-additive neighboring family). Let t ≥ 3 and let the two failed centers be r1 = (0, 0), r2 = (1 − t, t + 2) = g1 + 2g2 . (72) Then the three centers R = {(−t, t + 3), (0, −1), (0, 3)}
(73)
cover Bt (r1 ) ∪ Bt (r2 ). By reflection, the displacement (t − 1, −t − 2) = −(g1 + 2g2 ) also has a three-replacement repair. Proof. Let S1 = (−t, t + 3),
S2 = (0, −1),
S3 = (0, 3).
(74)
Again we use the three-strip membership test. First let z = (x, y) ∈ Bt (0, 0). If y ≤ t − 1 and x + y ≤ t − 1, then z ∈ Bt (S2 ). Otherwise y = t or x + y = t. If y = t, then x ≥ −t gives x + y ≥ 0 ≥ 3 − t for t ≥ 3. If x + y = t, then x ≤ t gives y ≥ 0 ≥ 3 − t. Thus in either case −t ≤ x ≤ t,
3 − t ≤ y ≤ t + 3,
3 − t ≤ x + y ≤ t + 3,
(75)
so z ∈ Bt (S3 ). Hence Bt (0, 0) ⊆ Bt (S2 ) ∪ Bt (S3 ). Now let z ∈ Bt (1 − t, t + 2). The failed-cell strips are 1 − 2t ≤ x ≤ 1,
2 ≤ y ≤ 2t + 2,
3 − t ≤ x + y ≤ 3 + t.
(76)
If x ≤ 0 and y ≥ 3, then z ∈ Bt (S1 ), since the x- and y-ranges and the full x + y-range agree with the strips of Bt (S1 ) on this part. Otherwise x = 1 or y = 2. If x = 1, then x + y ≤ 3 + t gives y ≤ t + 2 ≤ t + 3, and y ≥ 2 ≥ 3 − t. If y = 2, then x + y ≥ 3 − t gives x ≥ 1 − t ≥ −t. In either case z satisfies the three strips of Bt (S3 ). Hence Bt (1 − t, t + 2) ⊆ Bt (S1 ) ∪ Bt (S3 ).
(77)
Together the two containments prove the cover by the three centers in (73). The reflected case follows from (x, y) 7→ (−x, −y).
17
Figure 7: Extremal sectors used by the two-fault two-ball obstruction. The labels mark the axial transition sectors used in Lemma 8; any two-ball cover would have to satisfy incompatible strip inequalities on the two adjacent failed cells. Figure 7 marks the incompatible extremal sectors used in the two-ball impossibility argument; the labels in the figure match the transition inequalities used below. Lemma 8 (Two-ball impossibility for the non-additive families). For the two infinite nonadditive displacement families D = ±g2 and D = ±(g1 +2g2 ), no two replacement balls cover Bt (0) ∪ Bt (D). Consequently the three-ball constructions in Lemmas 6 and 7 are optimal. Proof. It is enough to prove the two positive representatives, because the negative representatives follow by the isometry (x, y) 7→ (−x, −y). Suppose first that D = g2 = (−t, 1) and that two translated radius-t balls cover Bt (0) ∪ Bt (D). Restricting the cover to Bt (0), the six extreme vertices force the two balls to occupy complementary axial arcs; no available replacement ball can contain an opposite pair of extremes, because such a pair fixes the center at the failed origin. Thus the two balls determine a single transition strip for Bt (0). Restricting the same two balls to Bt (D) forces another transition strip. In the coordinates of (67), the first transition requires the shared strip to satisfy x ≥ −t + 1 on the lower endpoint of the adjacent cell, whereas the second requires x ≤ −t on the corresponding endpoint of the central cell. These inequalities are incompatible. Equivalently, adding the two supporting-line inequalities gives 0 ≤ −1. For D = g1 + 2g2 = (1 − t, t + 2) we do not invoke an unverified symmetry reduction. Apply the axial automorphism T (x, y) = (y, −x − y),
(78)
which permutes the three strip coordinates by (x, y, x + y) 7→ (y, −x − y, −x) 18
(79)
and therefore preserves dEJ . The image of the second failed center is computed explicitly as T (1 − t, t + 2) = (t + 2, −3),
T (0, 0) = (0, 0).
(80)
Thus T maps the pair Bt (0) and Bt (1 − t, t + 2) to the pair Bt (0) and Bt (t + 2, −3). The supporting line x = −t of the original central hexagon is sent by T to the line X + Y = t in the image coordinates (X, Y ) = T (x, y), since X + Y = −x; this is one of the canonical supporting lines of Bt (0). Similarly, the adjacent supporting line x + y = 3 − t of the translated cell is sent to Y = t − 3, because Y = −x − y. Therefore, in the permuted strip coordinates (y, −x − y, −x), this image has the same adjacent-supporting-strip configuration as the D = g2 case: one transition side requires the common transition coordinate to be at most −t, while the other requires the same coordinate to be at least −t + 1. Written back in the original coordinates these two inequalities are x ≤ −t,
x ≥ −t + 1,
(81)
for the same transition line. They cannot hold simultaneously. Thus no two-ball cover exists for D = g1 + 2g2 either, and the reflected representatives follow by symmetry. Theorem 7 (Exact EJ two-fault non-additivity). For the four displacement families D ∈ {g2 , −g2 , g1 + 2g2 , −g1 − 2g2 },
(82)
with t ≥ 2 for ±g2 and t ≥ 3 for ±(g1 + 2g2 ), (2)
ρEJ (t, {0, D}) = 3.
(83)
Consequently, dense EJ two-fault repair is not universally additive. Proof. The upper bound three follows from the explicit covers in Lemmas 6 and 7 and their reflected images. The lower bound three follows from Lemma 8, which rules out any two-ball cover for the same four families. Thus the exact value is three. Independent one-fault repair would use four centers, so these families are genuinely non-additive. Remark 1 (Why this differs from the Gaussian case). The three-replacement families occur because two neighboring EJ hexagons can be cut into three axial sectors that are themselves contained in three translated radius-t hexagons. The analogous Gaussian failed cells are parity-constrained squares in rotated coordinates; the square-corner obstruction prevents this kind of three-sector cover. Thus the EJ two-fault result is not a repetition of the Gaussian additivity theorem, but a genuine hexagonal phenomenon. Lemma 9 (Axial endpoint rigidity). Let e ∈ {(1, 0), (0, 1), (1, −1)}
(84)
be one of the three axial directions of the EJ hexagon, and let two failed cells have centers 0 and D. Suppose that dEJ (D) > 2t,
dEJ (D + 2te) > 2t,
dEJ (D − 2te) > 2t.
Then every repair of Bt (0) ∪ Bt (D) requires at least four replacement balls. 19
(85)
Proof. Consider the two opposite axial endpoints of the first cell, p− = −te,
p+ = te,
(86)
and the corresponding two endpoints of the second cell, q − = D − te,
q + = D + te.
(87)
A radius-t EJ ball containing both p− and p+ must be centered at the midpoint 0. To see this algebraically, write e = (1, 0); the other two axial directions follow by the coordinate permutations preserving dEJ . If a center c = (a, b) satisfies dEJ (c, (t, 0)) ≤ t,
dEJ (c, (−t, 0)) ≤ t,
(88)
|a + t| ≤ t,
(89)
then the two x-strip inequalities give |a − t| ≤ t,
which force a = 0. With a = 0, the two (x + y)-strip inequalities give |b − t| ≤ t,
|b + t| ≤ t,
(90)
which force b = 0. Hence the only radius-t ball containing the opposite endpoints of the first failed cell is the failed ball centered at 0, which is unavailable. The same argument after translation shows that the only radius-t ball containing both q − and q + is the failed ball centered at D. It remains to exclude a single replacement ball covering one endpoint from each failed cell. The three possible cross differences between an endpoint of the first pair and an endpoint of the second pair are q τ − pσ = D + (τ − σ)te,
σ, τ ∈ {−1, 1},
(91)
so they are D, D + 2te, or D − 2te. By (85), each has EJ distance strictly larger than 2t. Since every radius-t ball has diameter at most 2t, no replacement ball can contain any such cross pair. Thus the four endpoint demands must be served by four distinct replacement balls. Therefore every repair has size at least four. Theorem 8 (Endpoint-rigid additive two-fault pairs). If a two-fault displacement D satisfies the endpoint-rigidity condition (85) for at least one axial direction e ∈ {(1, 0), (0, 1), (1, −1)}, then (2) ρEJ (t, {0, D}) = 4. (92) Proof. Lemma 9 gives the lower bound four. The independent two-cell repair of Theorem 6 gives the upper bound four. Hence the exact value is four. In the bounded neighboring audit, this endpoint-rigidity test covers the additive families whose resource-lattice displacement has no narrow diagonal corridor. More explicitly, for the tested neighboring displacement families, all stable additive classes except D = ±(g1 + g2 ) satisfy (85) for at least one of the three axial directions; the exceptional diagonal-corridor class is handled separately below. 20
Lemma 10 (Diagonal-corridor obstruction). Let t ≥ 3 and let the two failed centers be r1 = (0, 0),
r2 = g1 + g2 = (1, t + 1).
(93)
Then three radius-t replacement balls cannot cover Bt (0, 0) ∪ Bt (1, t + 1).
(94)
The same conclusion holds for the reflected displacement −(g1 + g2 ) = (−1, −t − 1). Proof. We prove the positive displacement; the reflected case follows from the isometry (x, y) 7→ (−x, −y). Put D = (1, t + 1),
U = Bt (0, 0) ∪ Bt (D).
(95)
The proof uses a finite boundary-demand set, but the argument is purely algebraic: each demand point is a closed-form function of t, and all exclusions are verified by the three strip inequalities defining dEJ . Consider the ten boundary points P0 = {(−t, 0), (−t, t), (0, −t), (t, −t), (t, 0)}, PD = {(1 − t, t + 1), (1 − t, 2t + 1), (1, 2t + 1), (t + 1, 1), (t + 1, t + 1)},
(96) (97)
and let P = P0 ∪ PD . The first five points lie on the boundary of Bt (0, 0), and the second five are the corresponding five boundary points of Bt (D). The omitted extreme points, (0, t) and (1, 1), are exactly the two extremes facing the narrow diagonal corridor. Thus P ⊆ U . We claim that every nonfailed radius-t ball contains at most three points of P. Let c = (a, b) be a center with c ̸= (0, 0) and c ̸= D. If Bt (c) contains four points of P0 , then the three strip coordinates of c are forced to be zero. Indeed, any four of the five points in (96) include two points on one pair of opposite supporting sides and one point on a second pair; applying the inequalities |x − a| ≤ t,
|y − b| ≤ t,
|x + y − a − b| ≤ t
(98)
to those boundary points gives successively a = 0, b = 0, and a + b = 0. Hence the only ball containing four of P0 is the failed ball Bt (0, 0), which is unavailable. Translating the same calculation by D shows that the only ball containing four of PD is the failed ball Bt (D), also unavailable. It remains to rule out mixed four-point coverage. A mixed four-point subset contains at least two points from one of the two five-point sets and at least two points from the other. Up to reversing the two failed cells and reflecting across the diagonal corridor, the possible two-point boundary types are represented by the following three strip separations: boundary type forced separation between the two pairs x-parallel pair |(t + 1) − (−t)| = 2t + 1, y-parallel pair |(2t + 1) − (−t)| = 3t + 1, (x + y)-parallel pair |(2t + 2) − 0| = 2t + 2. 21
(99)
Each displayed separation is strictly larger than 2t. Since any radius-t EJ ball has diameter at most 2t in every strip coordinate, no available radius-t ball can contain two boundary points of one failed cell and two boundary points of the other. Therefore an available radius-t ball contains at most three points of P. If three replacement balls covered U , then they would cover all ten points of P. But each available replacement ball covers at most three of these points, so three balls cover at most nine points of P, a contradiction. Hence at least four replacement balls are necessary for D = g1 + g2 . Reflection gives the same lower bound for D = −(g1 + g2 ). Theorem 9 (Diagonal-corridor additivity). For t ≥ 3 and D = ±(g1 + g2 ) = ±(1, t + 1),
(100)
we have (2)
ρEJ (t, {0, D}) = 4.
(101)
Proof. The lower bound four follows from Lemma 10. The upper bound four follows from independent two-cell repair. Hence the exact value is four. Remark 2 (Scope of the two-fault classification). The two-fault section uses four symbolic mechanisms: explicit three-ball covers for the stable non-additive families, two-ball impossibility for those same families, endpoint rigidity for additive pairs with separated opposite axial endpoints, and the diagonal-corridor obstruction for D = ±(g1 + g2 ). These theorems do not assert that every neighboring displacement is captured by a single closed formula; the bounded audit records the remaining tested neighboring cases and the small-radius exceptions. Lemma 11 (No shared candidate for distant failed cells). Let ri and rj be two failed resource centers. If dEJ (ri , rj ) > 4t, (102) then no radius-t replacement ball can intersect both Bt (ri ) and Bt (rj ). Proof. Suppose that a replacement center z has Bt (z) ∩ Bt (ri ) ̸= ∅,
Bt (z) ∩ Bt (rj ) ̸= ∅.
(103)
Choose vertices u ∈ Bt (z) ∩ Bt (ri ) and v ∈ Bt (z) ∩ Bt (rj ). Then dEJ (ri , rj ) ≤ dEJ (ri , u) + dEJ (u, z) + dEJ (z, v) + dEJ (v, rj ) ≤ 4t,
(104) (105)
contradicting the hypothesis. Corollary 2 (Separated two-fault repair). If two failed resources r1 , r2 satisfy dEJ (r1 , r2 ) > 4t, then (2) ρEJ (t, {r1 , r2 }) = 4. (106) Proof. The upper bound is Theorem 6. For the lower bound, Lemma 11 shows that every replacement ball can intersect at most one failed cell. Each failed cell requires at least two replacements by Theorem 3. Hence the two failed cells require at least four replacement balls. 22
9
Multi-Fault Repair Bounds and Dense-Cluster Subadditivity
Let F = {r1 , r2 , . . . , rq } ⊆ S
(107)
be the set of failed resources and let [
U (F ) =
Bt (r)
(108)
Bt (z).
(109)
r∈F
be the failed region. A repair set R is valid if U (F ) ⊆
[ z∈R
(q)
For a fixed failed set F , write ρEJ (t, F ) for the minimum number of replacements needed to cover U (F ). Theorem 10 (Independent q-fault upper bound). For every failed set F with |F | = q, (q)
ρEJ (t, F ) ≤ 2q.
(110)
Proof. For each failed resource r ∈ F , choose one translated canonical repair pair from (18), for example Rr = {r − (1, 0), r + t(1, 0)}. (111) By Corollary 1, Rr covers Bt (r). Therefore R=
[
Rr
(112)
r∈F
covers
S
r∈F Bt (r) = U (F ).
Since |R| ≤
P
r∈F |Rr | = 2q, the claimed upper bound follows.
Theorem 11 (Exact additivity for separated failures). Let F = {r1 , . . . , rq } be a failed resource set satisfying dEJ (ri , rj ) > 4t for all i ̸= j. (113) Then (q)
ρEJ (t, F ) = 2q.
(114)
Proof. The upper bound is the independent repair theorem. For the lower bound, Lemma 11 shows that every replacement ball can intersect at most one failed cell. Each individual failed cell requires at least two replacements by Theorem 3. Hence the q failed cells require at least 2q replacement balls in total. The lower and upper bounds agree. The separated theorem describes the additive regime. The clustered regime is more interesting. The clustered regime also contains small closed-form families whose optima can be proved directly. The next theorem gives a four-fault algebraic subadditivity result before the six-fault saving theorem and shows that the phenomenon is not confined to a single large example. 23
Theorem 12 (Exact dense four-fault cluster). Let Ct = {(−t, 1), (−1, −t − 1), (0, 0), (t − 1, −t − 2)}.
(115)
For every t ≥ 3, (4)
ρEJ (t, Ct ) = 4.
(116)
Thus four dense failed resource cells can be repaired with four replacements rather than the independent bound 2q = 8. Proof. First consider the four replacement centers St = {(−t − 1, 2), (−1, −t − 2), (1, 0), (t, −t − 2)}.
(117)
Using the three-strip representation of an EJ ball, direct interval substitution gives the following containment relations: Bt (−t, 1) ⊆ Bt (S1 ) ∪ Bt (S2 ) ∪ Bt (S3 ), Bt (−1, −t − 1) ⊆ Bt (S1 ) ∪ Bt (S2 ) ∪ Bt (S4 ), Bt (0, 0) ⊆ Bt (S1 ) ∪ Bt (S2 ) ∪ Bt (S3 ), Bt (t − 1, −t − 2) ⊆ Bt (S2 ) ∪ Bt (S4 ),
(118)
where S1 , . . . , S4 are listed in the order of (117). For example, a point in Bt (t − 1, −t − 2) that is not contained in Bt (S2 ) violates exactly the left axial strip relative to S2 ; the same strip inequality places it in Bt (S4 ). For the first containment in (118), the left extreme point p = (−2t, 1) of Bt (−t, 1) is covered by S1 = (−t − 1, 2) because dEJ (p, S1 ) = max{t − 1, 1, t} = t.
(119)
The opposite transition boundary of this same failed cell is handled by the S2 and S3 strips: substituting a boundary point (−t + u, 1 + v) with |u|, |v|, |u + v| ≤ t shows that failure of the S1 right strip leaves the point in the S3 interval, while failure of the S1 lower diagonal strip leaves it in the S2 interval. These are the same two shifted inequalities used in the displayed containment, and they cover the remaining boundary arcs. The other containments are analogous three-strip interval calculations. Hence St covers the four failed cells and (4) ρEJ (t, Ct ) ≤ 4. For the lower bound, define the four-point demand packing Zt = {(−2t, 1), (−1, −2t − 1), (0, t), (2t − 1, −t − 2)}.
(120)
These points lie in the four failed cells of (115), respectively. Their pairwise EJ distances are z2 z3 z4 z1 2t + 2 3t − 1 4t − 1 (121) z2 3t + 2 3t − 1 z3 2t + 2 all of which are strictly larger than 2t for t ≥ 3. Since every radius-t EJ ball has diameter at most 2t, one replacement ball can meet at most one point of this strict 2t-packing. Four (4) distinct replacement balls are necessary, so ρEJ (t, Ct ) ≥ 4, proving the theorem. 24
The exact optimizer repeatedly returned a six-fault pattern whose coordinates are independent of t when written in the resource-lattice basis g1 , g2 . In axial coordinates the family is Ft = {(−t, 1), (−1, −t − 1), (0, 0), (t − 1, −t − 2), (t, −1), (2t, −2)}.
(122)
Equivalently, in (m, n) resource-lattice coordinates with D = mg1 + ng2 , the same pattern is {(0, 1), (−1, −1), (0, 0), (−1, −2), (0, −1), (0, −2)}.
(123)
Thus the shape is a fixed dense two-column cluster in the resource lattice. Figure 8 illustrates this cluster, the five replacement balls, and the packing points for t = 3.
Figure 8: Dense six-fault EJ cluster for t = 3. The six failed resource cells in Ft are repaired by the five centers in Rt , while the marked packing points are pairwise farther than 2t and therefore give the demand-packing lower bound. This is the proof-supporting visualization (6) for the exact subadditivity theorem ρEJ (t, Ft ) = 5. Lemma 12 (Five-ball cover of the six-fault cluster). For every t ≥ 3, the failed region generated by Ft in (122) is covered by the five replacement centers Rt = {(−t − 1, 2), (−1, −t − 2), (2, t − 3), (t, −t − 2), (2t + 1, −2)}.
(124)
(6)
Therefore ρEJ (t, Ft ) ≤ 5. Proof. Membership in an EJ ball is the three-strip condition |x − c1 | ≤ t,
|y − c2 | ≤ t, 25
|x + y − c1 − c2 | ≤ t.
(125)
Substituting the six failed centers in (122) and the five repair centers in (124) gives the following strip-containment relations: Bt (−t, 1) ⊆ Bt (R1 ) ∪ Bt (R2 ) ∪ Bt (R3 ) ∪ Bt (R4 ), Bt (−1, −t − 1) ⊆ Bt (R1 ) ∪ Bt (R2 ) ∪ Bt (R4 ), Bt (0, 0) ⊆ Bt (R1 ) ∪ Bt (R2 ) ∪ Bt (R3 ) ∪ Bt (R4 ), Bt (t − 1, −t − 2) ⊆ Bt (R2 ) ∪ Bt (R4 ), Bt (t, −1) ⊆ Bt (R3 ) ∪ Bt (R4 ) ∪ Bt (R5 ), Bt (2t, −2) ⊆ Bt (R3 ) ∪ Bt (R4 ) ∪ Bt (R5 ),
(126)
where R1 , . . . , R5 denote the five centers in the order listed in (124). Each line of (126) is obtained by expanding (125). For example, the failed cell Bt (t − 1, −t − 2) is shared by R2 = (−1, −t − 2) and R4 = (t, −t − 2). A concrete boundary trace is the vertex p = (2t − 1, −t − 2) ∈ Bt (t − 1, −t − 2).
(127)
It is not in Bt (R2 ) because |px + 1| = 2t > t, but it is in Bt (R4 ) since |px − t| = t − 1,
|py + t + 2| = 0,
|px + py + 2| = t − 1.
(128)
Thus the same three strip inequalities that exclude p from the left repair ball place it inside the right repair ball. The symbolic interval calculation in (126) applies this interval check to every vertex of each failed cell. Taking the union of the six containments proves that Rt covers the whole failed region. Lemma 13 (Five-point demand packing). For every t ≥ 3, the failed region U (Ft ) contains a five-point demand packing Wt = {(3t, −2), (t − 1, t − 1), (−2t, t + 1), (2t − 1, −t − 2), (−t − 1, −t − 1)}
(129)
whose pairwise distances are all greater than 2t. Proof. Each demand point lies in the failed region. Specifically, (3t, −2) ∈ Bt (2t, −2), (−2t, t + 1) ∈ Bt (−t, 1), (−t − 1, −t − 1) ∈ Bt (−1, −t − 1).
(t − 1, t − 1) ∈ Bt (t, −1), (2t − 1, −t − 2) ∈ Bt (t − 1, −t − 2),
For any two vertices u, v, a radius-t ball can cover both only if dEJ (u, v) ≤ 2t. The pairwise distances among the five demand points are w1 w2 w3 w4
w2 2t + 1
w3 w4 w5 5t 2t + 1 5t 3t − 1 2t + 1 4t 4t − 1 2t + 2 3t 26
(130)
where w1 , . . . , w5 are ordered as in (129). For t ≥ 3 every displayed distance is strictly larger than 2t; the binding entry is 3t − 1, which already exceeds 2t for every t > 1. The construction also covers the boundary case t = 3, where the third repair center in (124) becomes (2, 0) and all displayed strip inequalities remain valid. Since the diameter of a radius-t EJ ball is at most 2t, any single replacement ball can cover at most one point of this packing. Therefore at least five replacement balls are necessary. Theorem 13 (Exact dense six-fault subadditivity). For the six-fault cluster Ft in (122), and every t ≥ 3, (6) ρEJ (t, Ft ) = 5. (131) Consequently, the independent bound 2q = 12 can overestimate the optimum by seven replacements. (6)
Proof. The five-ball construction above gives ρEJ (t, Ft ) ≤ 5. The five-point demand-packing lemma gives the reverse inequality. Therefore the exact value is five. The six-fault theorem is included not as a numerical curiosity but as a structural result: dense EJ clusters can share repair balls across several adjacent failed service cells. This behavior is impossible in the separated regime and is much stronger than the two-fault drop from four to three. Remark 3 (Role of the t ≤ 12 multi-fault audit). The dense four-fault and six-fault cluster theorems above are symbolic results valid for all t ≥ 3; they do not depend on extrapolating the finite audit. The audit is used in the same role as in the Gaussian local-repair paper: it validates the tested finite search space, validates the implementation of the coverage and overlap identities, and exposes additional patterns for future closed-form classification. The main mathematical claims in this section are the universal 2q upper bound, separated additivity, the exact four-fault cluster, the exact six-fault cluster, and the inclusion–exclusion overlap identity.
10
Exact Multi-Fault Overlap Accounting
For multiple failures, the replacement number is not the only useful quantity. Independent local repairs may interact, creating vertices of the failed region that are covered two, three, or more times by replacement balls. The following identity is unconditional: it applies to any valid repair set in any failed region. For z ∈ U (F ), define the replacement multiplicity µR (z) = |{r ∈ R : z ∈ Bt (r)}|. The true overlap mass inside the failed region is X O(R) = (µR (z) − 1). z∈U (F )
27
(132)
(133)
For j ≥ 2, define X µR (z)
Pj (R) =
j
z∈U (F )
.
(134)
Thus P2 (R) is the total pairwise common-intersection mass, P3 (R) is the total triple-intersection mass, and so on. Lemma 14 (Vertexwise binomial identity). For every integer m ≥ 1, m X j m m−1= (−1) . j j=2 Proof. The binomial identity
Pm
j m j=0 (−1) j
(135)
= 0 gives
m X
m 1−m+ (−1) = 0, j j=2 j
(136)
which is equivalent to the stated formula. Theorem 14 (Exact multi-failure overlap identity). For any valid repair R of any failed resource set F , M X O(R) = (−1)j Pj (R), (137) j=2
where M = max µR (z).
(138)
z∈U (F )
Proof. Apply the vertexwise identity to m = µR (z) at each z ∈ U (F ) and sum over all failed-region vertices. Exchanging the finite sums gives exactly (137). Corollary 3 (Triple-core specialization). If a valid repair set R satisfies maxz∈U (F ) µR (z) ≤ 3, then O(R) = P2 (R) − P3 (R). (139) Moreover, if C3 (R) is the number of failed-region vertices covered by exactly three replacement balls, then P3 (R) = C3 (R) and O(R) = P2 (R) − C3 (R).
(140)
Proof. When the maximum multiplicity is at most three, all terms Pj with j ≥ 4 vanish. µR (z) Also is one exactly at vertices with multiplicity three and zero elsewhere. 3 For an independent canonical repair of q failed EJ cells, the additive one-cell overlap prediction is Aq = qt2 . (141) The extra dense-core overlap is Ωextra (R) = O(R) − Aq . 28
(142)
Combining this definition with the exact multi-failure overlap identity gives the general correction formula M X Ωextra (R) = (−1)j Pj (R) − qt2 . (143) j=2
If a repair has M ≤ 3, this reduces to Ωextra (R) = P2 (R) − C3 (R) − qt2 .
(144)
Example 3 (Multiplicity-four overlap accounting). The full formula is needed in EJ dense clusters. One certified audit row has t = 4, three failed resources F = {(−4, 1), (−1, −5), (0, 0)},
(145)
R = {(−5, 2), (−1, −6), (1, −1), (1, 0)}.
(146)
and four replacement centers
The computed multiplicity profile has maximum multiplicity M = 4 and P2 = 95,
P3 = 20,
P4 = 1.
(147)
Therefore the true repeated-coverage mass is O(R) = P2 − P3 + P4 = 95 − 20 + 1 = 76.
(148)
This example also shows why the triple-core shortcut is not universal. The same row has sixteen vertices of exact multiplicity three and one vertex of multiplicity four; the multiplicityfour vertex contributes 43 = 4 to P3 and 44 = 1 to P4 . Thus replacing P3 by only the number of exactly triple-covered vertices would give the wrong overlap. The additive onefault prediction for this row is 3t2 = 48, so the dense-core excess is 76 − 48 = 28.
11
Exact Validation and Audit
The theorems above are geometric and do not rely on simulation, but the implementation was audited in the same spirit as the Gaussian local-repair study. The one-fault audit exhaustively enumerated all candidates in B2t (0)\{0} for 1 ≤ t ≤ 20, minimized repair count and then overlap, and confirmed ρEJ (t) = 2, ΩEJ (t) = t2 , and the 3t canonical optimumpair count for every tested radius. The targeted two-fault audit enumerated all neighboring displacements D = mg1 + ng2 with dEJ (0, D) ≤ 4t for 2 ≤ t ≤ 20 and solved 832 exact set-cover instances: 78 have K = 3, 754 have K = 4, and no row is unresolved. The stable K = 3 rows are the infinite families D = ±g2 and D = ±(g1 + 2g2 ) proved above; the additional K = 3 rows occur only at t = 2 and t = 4 and are recorded as finite short-corridor exceptions. The multi-fault optimizer solved 19,400 exact instances for 2 ≤ t ≤ 12 and 3 ≤ q ≤ 6 in clustered, line, pair-plus, triangle, and random-local modes. The optimum replacement counts show strong subadditivity: maximum savings relative to independent repair were 2, 29
4, 5, and 7 for q = 3, 4, 5, 6, respectively, and maximum replacement multiplicity was 4. The smooth increase in average saving across q reflects the balanced audit design and the growing number of dense local sharing opportunities, not a proved asymptotic law. Every audit row records failed centers, replacement centers, uncovered vertices, multiplicity counts, higher-order coverage masses, and inclusion–exclusion residuals; the residual is zero in all rows. The audit is therefore a reproducibility and pattern-discovery layer, while the universal mathematical claims are the one-fault formulas, the symbolic two-fault mechanisms, separated additivity, the dense four- and six-fault cluster theorems, and the overlap identity.
12
Conclusion
This paper introduced local fault repair for perfect resource placements in dense Eisenstein– Jacobi networks. After one resource fails, the uncovered region is exactly the former hexagonal service cell, and every useful replacement lies within distance 2t of the failed resource. A single nonfailed replacement cannot cover the failed cell, while two explicitly placed replacements always do. Hence ρEJ (t) = 2 for every t ≥ 1. Among all minimum-size repairs, every two-ball cover has at least t2 repeated vertices inside the failed cell, and the canonical axial repair attains this bound exactly. Thus ΩEJ (t) = t2 . For two failed resources, EJ repair is not universally additive. Four replacements always suffice by independent repair, but two infinite neighboring displacement families admit threereplacement repairs. Additive behavior is proved algebraically for endpoint-rigid pairs, for the diagonal-corridor pair D = ±(g1 + g2 ), and for separated failed cells. A targeted exact optimizer for 2 ≤ t ≤ 20 classified 832 neighboring displacement cases, finding 78 nonadditive K = 3 cases and 754 additive K = 4 cases with no unresolved rows, in agreement with the symbolic mechanisms and the listed small-radius exceptions. This separates the EJ theory from the Gaussian local-repair paper, where the two-fault value is additive for all displacements. For multiple failed resources, the paper proves both an additive regime and a densecluster subadditive regime. Independent canonical repair gives a 2q upper bound for q failed resources, and this bound is exact whenever failed cells are pairwise more than 4t apart. In contrast, a fixed four-fault dense cluster has exact repair number four and a fixed six-fault dense cluster has exact repair number five for every t ≥ 3, giving savings of four and seven replacements relative to independent repair. The exact multi-fault audit for 2 ≤ t ≤ 12 confirms that this subadditivity is common in clustered EJ failures. Finally, repeated coverage inside any failed region is governed by an exact inclusion–exclusion identity over replacement multiplicities. Together these results show that local repair in Eisenstein– Jacobi placements has a distinct hexagonal theory: one-fault overlap is quadratic, two-fault repair can be non-additive, and dense multi-fault clusters can reuse replacement balls across several failed service cells.
Acknowledgments The author thanks the Department of Computer Science, Faculty of Science, Kuwait University, for its support and research environment. This work did not receive a specific grant 30
from any funding agency in the public, commercial, or not-for-profit sectors.
Declaration of competing interest The author declares that he has no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Data availability The validation data and audit data generated during the current study are available from the author upon reasonable request.
Declaration of generative AI and AI-assisted technologies in the writing process During the preparation of this work, the author used an AI-assisted language tool, to support manuscript wording refinement, and LaTeX preparation. The author reviewed and edited all AI-assisted output and takes full responsibility for the content of the published article.
References [1] M. Flahive and B. Bose, “On resource placement in Gaussian and EJ interconnection networks,” IEEE Transactions on Computers, vol. 62, no. 3, pp. 623–626, Mar. 2013. [2] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, Aug. 2010. [3] C. Martı́nez, E. Stafford, R. Beivide, and E. M. Gabidulin, “Modeling hexagonal constellations with Eisenstein–Jacobi graphs,” Problems of Information Transmission, vol. 44, no. 1, pp. 1–11, 2008. [4] M. M. Bae and B. Bose, “Resource placement in torus-based networks,” IEEE Transactions on Computers, vol. 46, no. 10, pp. 1083–1092, Oct. 1997. [5] P. Ramanathan and S. Chalasani, “Resource placement with multiple adjacency constraints in k-ary n-cubes,” IEEE Transactions on Parallel and Distributed Systems, vol. 6, no. 5, pp. 511–519, May 1995. [6] N.-F. Tzeng and G.-L. Feng, “Resource allocation in cube network systems based on the covering radius,” IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 4, pp. 328–342, Apr. 1996.
31
[7] M. Livingston and Q. F. Stout, “Perfect dominating sets,” in Proceedings of the TwentyFirst Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, vol. 79, pp. 187–203, 1990. [8] W. F. Klostermeyer, “A taxonomy of perfect domination,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 18, nos. 1–2, pp. 105–116, 2015. [9] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, no. 7, pp. 839–854, 2013. [10] S. Prabhu, V. Manimozhi, M. Arulperumjothi, and S. Klavžar, “Twin vertices in faulttolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks,” Applied Mathematics and Computation, vol. 420, Art. 126897, May 2022. [11] E. Cheng, Y. Mao, K. Qiu, and Z. Shen, “A general approach to deriving diagnosability results of interconnection networks,” Journal of Interconnection Networks, vol. 22, no. 3, Art. 2250011, 2022. [12] L. Girish and K. Somasundaram, “Bound for the k-fault-tolerant power-domination number,” Symmetry, vol. 16, no. 7, Art. 781, 2024. [13] A. Thomson and S. Zhou, “Frobenius circulant graphs of valency six, Eisenstein–Jacobi networks, and hexagonal meshes,” Journal of Algebraic Combinatorics, vol. 38, pp. 273– 300, 2013. [14] B. Albader, B. Bose, and M. Flahive, “Efficient communication algorithms in hexagonal mesh interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 69–77, Jan. 2012.
32