arrays.md

The objects

A sparse array is a finite set S of integer sensor positions; its difference coarray is D(S) = S - S, and its weight w_S(t) counts the ordered pairs (p, q) in S^2 with p - q = t, so w_S(0) = card S. A sensor s is essential when removing it changes the coarray, D(S - {s}) != D(S), the fragility is the share of essential sensors, and S is maximally economic when every sensor is essential. The words are Cohen and Eldar 2020, Definitions 9 to 11, who take them from Liu and Vaidyanathan; the arrays serve direction finding, where a lost lag breaks the coarray estimator.

• The generator G is a set of L >= 2 sensors, shifted so that min G = 0, whose coarray is hole-free: D(G) = [-a, a] with a = max G. The base is M = 2a + 1 = card D(G), the translation factor of Cohen and Eldar.
• The fractal array of order r is F_r = {sum_(i<r) g_i M^i : g_i in G}, the dim 1 digit design with base M and digit set G at level r; Cohen and Eldar grow it as F_(r+1) = union over g in G of (F_r + g M^r), which is the same set. The Cantor set array is G = {0, 1}, M = 3.
• U(G) is the set of paired sensors, g in G with some h in G such that w_G(g - h) = 1, and u = card U(G). Cohen and Eldar's condition C1 says every sensor is paired, U(G) = G; their Lemma 1 (from Liu and Vaidyanathan) says a paired sensor is essential. E(G) is the set of essential sensors of G, so U(G) sits inside E(G).
• Every number below is printed by the study lab/py/fractal-array-fragility, whose sweep is every hole-free generator with L <= 6 and span a <= 13, one of each mirror pair: 119 generators. Its test of essentialness is the definition itself, remove the sensor and recompute the coarray.

The weight is a product over digits

Every lag t of F_r has one expansion t = sum_(i<r) t_i M^i with balanced digits t_i in [-a, a], and w_(F_r)(t) = prod_(i<r) w_G(t_i). Proved. A difference of two sensors is sum (g_i - h_i) M^i with every digit difference in [-a, a], and M = 2a + 1 is exactly the number of balanced digits, so the expansion is the balanced base-M expansion and is unique; an ordered pair of sensors with difference t is therefore a tuple of r ordered digit pairs, the i-th with difference t_i, and they are counted independently. So the coarray is [-(M^r - 1)/2, (M^r - 1)/2], hole-free, which is Cohen and Eldar's Theorem 1, and the weight is the digit-by-digit product that their Theorem 4 writes as a convolution; in the frequency variable it is the product prod_i abs(P_G(M^i x))^2 of the generator's array factor at the scales M^i, the fractal product beampattern.

The Cantor array is the case G = {0, 1}: w_G(0) = 2 and w_G(1) = w_G(-1) = 1, so the weight of t is 2 to the number of zero digits of t in balanced ternary, the R_A(t) = 2^(z_3(t)) of the energy reduction in cobham, Object S. The sumset of that note and the array of this one carry the same product.

Fragility is exact

Theorem A. Let G be hole-free on [-a, a], M = 2a + 1 and r >= 2. A sensor s of F_r is essential exactly when every base-M digit of s lies in U(G). So F_r has exactly u^r essential sensors and its fragility is (u/L)^r. Proved.

• Removing s deletes the lag t != 0 exactly when every ordered pair with difference t contains s; those pairs are at most two, (s, s - t) and (s + t, s). So s is essential exactly when some t != 0 has w(t) <= 2 with all its pairs through s.
• If all digits of s are paired, pick h_i with w_G(s_i - h_i) = 1 and put h = sum h_i M^i. The lag s - h has every digit weight 1, so weight 1, and its one pair is (s, h): s is essential.
• If w(t) = 1 and its pair is (s, q) or (q, s), every digit pair is the unique pair for t_i, and t_i != 0 because w_G(0) = L >= 2; so every digit of s is paired.
• If w(t) = 2 with both pairs through s, the pairs are (s, s - t) and (s + t, s), and the product puts weight 2 on one digit j and weight 1 on every other. Pick i != j, which needs r >= 2: the two pairs share the unique digit pair for t_i, so s_i = (s + t)_i and (s - t)_i = s_i, which gives t_i = 0 and w_G(t_i) = L >= 2, a contradiction. So weight 2 never makes a sensor essential, and the three cases close the proof.

Verified against the definition: on all 119 generators at r = 2 and r = 3, 238 cases up to 216 sensors, the set of sensors whose removal changes the recomputed coarray equals the set of sensors with all digits in U(G), with 0 mismatches (lab/py/fractal-array-fragility, verb exact). The theorem is false at r = 1, and that is the whole gap the next section measures: G = {0, 1, 2} is maximally economic, its middle sensor killing the lags +-1 of weight 2, yet U(G) = {0, 2}, so F_2 at M = 5 has 4 essential sensors of 9 and F_3 has 8 of 27.

The two bounds

Two bounds are in print, both read at source. Cohen and Eldar 2020, Theorem 5: if G satisfies C1 then so does F_r, hence F_r is maximally economic; Theorem 6: the fragility of F_r is at most that of G. Yang, Shen, Liu, Eldar and Cui 2023, Part II, Lemma 1: an inessential sensor of G or of F_r passes its inessentialness to every sensor of F_(r+1) built on it; Proposition 1: the fragility of F_r is at most the r-th power of that of G. Both are one-way.

• The converse of Theorem 5: for r >= 2, F_r is maximally economic exactly when G satisfies C1, and exactly then Theorem 6 is attained, (u/L)^r = card E(G)/L. Proved (Theorem A: every sensor is essential exactly when u^r = L^r, that is U(G) = G; if u < L then (u/L)^r < u/L <= card E(G)/L, and u >= 2 because the lag a has the one pair (a, 0)). At r = 1 the converse fails on G = {0, 1, 2}.
• For r >= 2, Proposition 1 is tight, (card E(G)/L)^r = (u/L)^r, exactly when every essential sensor of G is paired, E(G) = U(G); otherwise it is strictly loose at every r >= 2. Proved (Theorem A, with U(G) inside E(G)). The verb exact prints the criterion with 0 failures on the 238 cases, which follows from its Theorem A check and is not separate evidence.
• A sensor in E(G) but not in U(G) is the middle of a three-term progression g - t, g, g + t in G whose step has weight exactly 2: the weight-2 case of the proof, which is live at r = 1 and dies at every r >= 2.
• Of the 119 generators, 21 are loose, and 14 of those 21 are maximally economic, so both published bounds print 1 while the fragility is (u/L)^r and tends to 0. Verified (lab/py/fractal-array-fragility, verb exact, which lists the 21). The 14 run from {0, 1, 2} and {0, 1, 2, 4} through {0, 1, 4, 5, 7} to generators with six sensors such as {0, 1, 3, 5, 8, 9}, and on every one of the 21 the excess card E(G) - u is 1, as the study prints.
• The minimum redundancy array {0, 1, 4, 6} satisfies C1 and stays at fragility 1 at every order, where both bounds are tight. {0, 1, 2, 3} has u = 2 = card E(G), so Proposition 1 is tight while Theorem 6 is not: F_2 at M = 7 has 4 essential sensors of 16, fragility 1/4 against the bound 1/2.

The compressed base

Cohen and Eldar set the base by the generator's coarray, M = 2a + 1, where the earlier fractal arrays they cite take any natural translation factor; the digit design allows any base b with a < b <= 2a + 1, and below 2a + 1 a lag has many balanced expansions, joined by carries.

• For a < b <= 2a + 1 the digit design with base b and digits G at level r has L^r sensors and the hole-free coarray [-A, A], A = a(b^r - 1)/(b - 1). Proved. Digits below b make the sensors distinct; the lags at level r + 1 are d + b x with d in [-a, a] and x in [-A_r, A_r], and consecutive x give intervals of length 2a + 1 >= b that abut or overlap. Verified on every row below (lab/py/fractal-array-fragility, verb dial, which asserts both).
• The essential count e_r(G, b) is no longer a product. Verified (lab/py/fractal-array-fragility, verb dial, up to 16384 sensors and 8 million lags, the fast test checked against the definition up to 250 sensors):

• Every row satisfies, from r = 2 or r = 3 on, an affine law e_(r+1) = lambda e_r + c with an integer lambda between 1 and u: bounded at lambda = 1 with c = 0, geometric at 1 < lambda < u, and the full u^r. Conjecture (the verb dial fits lambda >= 1 and c on two steps, taking lambda = 1 on a flat tail, no upper bound, then checks the law on the next 1 to 4 steps; every fitted lambda is an integer in [1, u], and the ratios seen are 1, 2, 3, 4, 5). {0, 1, 4, 6} at base 8 is e_r = 7 2^(r-1) - 3 and {0, 1, 2, 3, 7, 11} at base 15 is 5 2^r - 4 on the printed terms.
• The full law arrives before 2a + 1: at b = 9, 14, 14 and 20 for spans 6, 7, 9 and 11, against M = 13, 15, 19 and 23. Theorem A's proof reaches no further than uniqueness of the balanced expansion, so these rows are data, not theorem.
• What the dial buys, said plainly: {0, 1, 2} at base 4 has 3^r sensors, 2 essential ones at every r from 2 to 8, the fragility 2/N of the uniform line at base 3, (4^(r+1) - 1)/3 hole-free lags, a product array factor prod_i P_G(4^i x) and a self-similar layout; at r = 8 that is 6561 sensors and 87381 lags. That is not a record for lags: they grow as N^(log 4/log 3), about N^1.26, while the minimum redundancy array reaches order N^2 lags and is maximally economic (Liu and Vaidyanathan 2019, Part II). Whether a closed-form array has fragility 2/N and order N^2 lags is not settled here; the gain is exact robustness in closed form with a product beampattern at every size.

What is open

• The thresholds of the compressed base: the least b where the full u^r law starts, and where the geometric regime starts, as functions of G. A lag at base b < 2a + 1 is read by a carry automaton on digit pairs, in the manner of the transfer matrices of beneath and transfer matrix, so e_r(G, b) should have a rational generating function; neither the automaton nor the function is built here.
• The k-essential family: the sets of k sensors whose joint removal changes the coarray while no smaller part does, the k-essential Sperner family of Liu and Vaidyanathan 2019. Their Part II, Lemma 1, gives it for every maximally economic array, the Cantor arrays among them: the single sensors and nothing larger; so for a generator with C1 it follows from Theorem 5 of Cohen and Eldar. For the others, a lag of F_r loses all its pairs to k removals only if its weight is at most 2k, which is the product law again, so the family should be a product of per-digit families at r large enough; it is not attempted here.
• The higher-order fractals of Yang, Shen, Liu, Eldar and Cui, where the coarray is a sum of q differences; their Proposition 2 is again an upper bound.

Where the numbers live

• lab/py/fractal-array-fragility: the verb exact (Theorem A against the definition, the tightness criterion, the 21 loose generators) and the verb dial (the compressed base table and its affine fits).
• The figure is F_4 of {0, 1, 2, 4} at M = 9, folded into the plane by alternating digits, its 81 essential sensors apart from the other 175; the binary asserts Theorem A on all 256 sensors against the definition.