Motivation

Consider the source program

for i in range(a):
    for j in range(b):
        work(i, j)

and a flattened implementation

for k in range(N):
    work_flat(k)       # N = a*b

The programs may perform the same work and produce the same outputs, yet the second representation does not by itself identify the original shape \((a,b)\). When \(N=12\), the ordered shapes \((2,6),(3,4),(4,3)\), and \((6,2)\) are all compatible with the flattened count. The computation is preserved; source geometry is not.

This distinction matters whenever later stages attempt to recover, explain, debug, reroll, or parallelize optimized code. Compiler infrastructures contain explicit loop-flattening transformations, while decompilation and loop-rerolling research address the inverse problem of recovering higher-level repetition from lower-level representations [2, 5, 3]. Existing quantitative information-flow work measures uncertainty about hidden values from observable program behavior [6, 1]. Here the hidden variable is instead the source-level loop structure.

Model and structural ambiguity

A perfectly rectangular, ordered loop nest of depth \(d\) is represented by \[M=(n_1,\ldots,n_d)\in\mathbb{N}_{\ge 2}^{d}.\] Its idealized flattening retains only \[F(M)=\prod_{i=1}^{d} n_i=N.\] The model intentionally suppresses index expressions, memory traces, debug metadata, and compiler conventions. Those can be added later as observations; the present question is what can be reconstructed from \((N,d)\) alone.

Ordered dimensions are essential: \((2,6)\) and \((6,2)\) induce different coordinate maps even though they have the same product. The maximum possible depth is \[\Omega(N)=\sum_{j=1}^{r}\alpha_j\] when \(N=\prod_{j=1}^{r}p_j^{\alpha_j}\); every loop bound must consume at least one prime factor.

If compatible shapes are equiprobable, the residual structural uncertainty is exactly \[H(M\mid N,d)=\log_2 K_d(N).\] For a nonuniform prior it is instead the posterior entropy over \(\mathcal{M}_{N,d}\). The counting quantity \(K_d(N)\) is prior-free and controls worst-case identifiability.

Exact ambiguity counting

Write the prime factorization of the flattened count as \[N=\prod_{j=1}^{r}p_j^{\alpha_j}.\] Every source dimension can be written \[n_i=\prod_{j=1}^{r}p_j^{e_{ji}},\] where each row of the exponent matrix \((e_{ji})\) sums to \(\alpha_j\). A zero column corresponds to the forbidden factor \(n_i=1\).

The formula is an inclusion–exclusion representation of the ordered factorization function with exactly \(d\) factors, a classical object in multiplicative partition theory [7]. Its role here is operational: it counts the source shapes erased by the transformation.

Exact reconstruction cost

Suppose an auxiliary metadata string \(Z\) is attached to the flattened representation and must identify the original member of \(\mathcal{M}_{N,d}\).

Define the real-valued structural deficit \[\Delta_B(N,d)=\log_2K_d(N)-B.\] The sign of \(\Delta_B\) gives a clean point-of-no-return criterion: if \(\Delta_B>0\), no metadata scheme of capacity \(B\) can distinguish all compatible sources. If the source shape is random with posterior \(P(M\mid N,d)\), the corresponding average description-length lower bound is \(H(M\mid N,d)\) by source coding [4]. The fixed-length theorem is stronger in the worst case and requires no prior.

Prime powers and the depth law

The cleanest depth dependence occurs when \(N=p^m\).

This law is nonmonotone in depth. There is one possible shape at \(d=1\), namely \((p^m)\), and one at \(d=m\), namely \((p,\ldots,p)\). Intermediate depths allow many allocations of exponent mass and are therefore harder to reconstruct.

Let \[q=\frac{d-1}{m-1}.\] Stirling’s approximation gives \[\log_2\binom{m-1}{d-1} =(m-1)h_2(q)-\frac12\log_2\!\bigl(2\pi(m-1)q(1-q)\bigr)+o(1),\] where \(h_2(q)=-q\log_2q-(1-q)\log_2(1-q)\) is binary entropy. Its derivatives are \[h_2'(q)=\log_2\frac{1-q}{q}, \qquad h_2''(q)=-\frac{1}{\ln2}\left(\frac1q+\frac1{1-q}\right)<0.\] Thus the unique continuous maximum occurs at \(q=1/2\), giving the discrete maximizers nearest \[\boxed{d^\star=\frac{m+1}{2}.}\] We call this the mid-depth ambiguity principle: for a fixed prime-power workload, intermediate-depth source nests are the least identifiable after flattening.

If depth is also erased, summing over all possible depths yields \[\sum_{d=1}^{m}\binom{m-1}{d-1}=2^{m-1}.\] Hence a flattened \(p^m\) workload with unknown depth loses exactly \(m-1\) fixed-length bits of boundary-pattern information.

The ambiguity polynomial

The whole depth profile can be collected into one program invariant.

Let \(N=\prod_{j=1}^{r}p_j^{\alpha_j}\) and introduce formal variables \(\mathbf{x}=(x_1,\ldots,x_r)\). A valid loop dimension corresponds to a nonzero exponent vector, whose multivariate generating function is \[G(\mathbf{x})=\prod_{j=1}^{r}\frac{1}{1-x_j}-1.\] Therefore \[K_d(N)= [x_1^{\alpha_1}\cdots x_r^{\alpha_r}]G(\mathbf{x})^d,\] and summing the geometric series in \(d\) gives \[\boxed{ \mathcal{A}_N(z)= [x_1^{\alpha_1}\cdots x_r^{\alpha_r}] \frac{zG(\mathbf{x})}{1-zG(\mathbf{x})}.}\]

The identity says that alternating cancellation across all possible source depths detects whether the flattened count is squarefree. We do not claim the number-theoretic identity itself as new; it is a natural consequence of ordered-factorization convolution. Its value here is that it gives the ambiguity polynomial a compact arithmetic signature.

Prototype calculation and implications

The exact formula is easy to evaluate once \(N\) is factored. The following direct implementation mirrors Theorem 2.

def ambiguity(exponents, depth):
    total = 0
    for q in range(1, depth + 1):
        weak = prod(comb(a + q - 1, q - 1)
                    for a in exponents)
        total += (-1)**(depth-q) * comb(depth, q) * weak
    return total

def recovery_bits(exponents, depth):
    K = ambiguity(exponents, depth)
    return 0 if K <= 1 else ceil(log2(K))

The profile is sensitive not merely to the magnitude of \(N\) but to its prime-exponent geometry. For example, \(N=2^{12}=4096\) has profile \[1,11,55,165,330,462,462,330,165,55,11,1,\] whereas a squarefree number with twelve prime factors follows the ordered set-partition counts \(d!\,S(12,d)\) and has a markedly different shape. Thus total work alone does not smoothly predict reconstructability: arithmetic structure and source depth jointly determine the loss.

The framework also separates three questions that are often conflated:

• Semantic preservation: does the transformation preserve observable behavior?

• Structural identifiability: how many source structures remain compatible?

• Algorithmic recovery: how hard is it to find the correct source given additional traces or metadata?

This paper addresses the second exactly for a deliberately minimal model. The bit bound is a capacity result, not a runtime-complexity claim.

Related work, limitations, and directions

Ordered factorizations. The coefficients \(K_d(N)\) are ordered factorizations with a prescribed number of factors, studied as arithmetic functions and through generating series [7]. Our exact formula is a direct inclusion–exclusion form; the new perspective is to treat the coefficient as transformation-induced source ambiguity.

Loop transformations and reconstruction. LLVM implements a pass that flattens nested loop pairs into one loop [2]. In the reverse direction, loop rolling and rerolling reconstruct repeated structure from low-level code or hardware descriptions [3, 5]. Those systems infer structure from rich syntactic and semantic evidence. Our model asks what is possible when only the total iteration count and depth survive.

Quantitative information flow. QIF uses entropy, vulnerability, and channel models to quantify what observations reveal about hidden values [6, 1]. We use the same basic language of residual uncertainty but assign the hidden variable to source structure rather than secret input.

Limitations. We assume rectangular nests, constant integer bounds, known ordering, no early exits, and an observation model that suppresses index arithmetic and memory behavior. Real optimized programs may retain enough evidence to make the ambiguity class much smaller. Conversely, syntactically distinct programs may be considered equivalent by a richer source model. The present result is therefore a baseline: it isolates information erased by the product map itself.

Promising extensions. The closest next step is partial boundary retention: quantify \(H(M\mid N,Z)\) when \(Z\) reveals selected loop boundaries or dimensions, then optimize which markers a compiler should preserve per metadata bit. Other promising directions are transformation composition, where structural uncertainty should be monotone under further deterministic erasure; irregular domains with dependent bounds; and empirical comparison of the theoretical ambiguity with rerolling or decompilation success. More speculative directions include a time-indexed recovery horizon over compiler passes and connecting erased iteration-space geometry to uncertainty about available parallelism.

A dynamic recovery horizon. Let \(X_0,X_1,\ldots,X_T\) be successively transformed representations of a source structure \(M\), with \(M\to X_t\to X_{t+1}\) a Markov chain. Define the residual structural loss at stage \(t\) by \[L_t=H(M\mid X_t).\] Data processing gives \(I(M;X_{t+1})\le I(M;X_t)\) and therefore \(L_{t+1}\ge L_t\): deterministic post-processing cannot recreate distinctions already absent from the current representation. Under a future metadata budget of \(B\) bits, define \[\tau_B=\min\{t:L_t>B\}.\] At and after \(\tau_B\), no auxiliary tag of capacity \(B\) can guarantee exact source recovery, since exact recovery from \((X_t,Z)\) would require \(H(M\mid X_t)\le H(Z)\le B\). This is a standard information-theoretic consequence rather than a new inequality, but transformation-specific estimates of \(L_t\) or \(\tau_B\) could connect the static counting theory to real compiler pipelines.

Claim boundary. The paper does not present the ordered-factorization formulas, source-coding bound, or Möbius function as new mathematics in isolation. The proposed contribution is the synthesis: a semantics-preserving transformation induces a finite source ambiguity class; its depth profile is exactly computable for loop flattening; and its logarithm has an operational meaning as the smallest worst-case reconstruction tag. A stronger full paper would need either a broader class of transformations, a compiler implementation that selects minimal structural metadata, or evidence that \(K_d(N)\) predicts practical reconstruction difficulty.

Conclusion

Loop flattening can preserve every execution while erasing a precisely countable amount of source geometry. For rectangular nests, that geometry is an ordered factorization class. Its cardinality gives an exact ambiguity measure; its logarithm gives the minimum reconstruction information; and its dependence on depth exposes a sharp mid-depth maximum for prime-power workloads. The result is intentionally small, but it provides a concrete model in which structural preservation can be discussed quantitatively rather than informally.