Optimal Radix $q$ under Resource Constraints: A Reconciled Derivation Framework for Ultrametric Hierarchies

In plain language

The paper tried to figure out which branching factor q to use when building a tree that organizes a million items, given limits on storage and how often the tree is walked through. By solving the math, the authors showed that the ideal continuous value of q is the natural number e ≈ 2.718, but when q must be an integer the best choice is q = 4 for equal importance of storage and traversal. They also found that q = 3 becomes better only when the cost of walking the tree (the traversal weight β) is higher than a threshold β* = 2.286, while q = 2 is never optimal for any positive β. For a million items, padding the tree with dummy leaves adds overhead of 4.86 % for q = 2, 59.43 % for q = 3, 4.86 % for q = 4, and 95.31 % for q = 5, and the overall scores still rank q = 4 as the winner. This matters because choosing the right q reduces wasted storage and speeds up searches, making large hierarchical data structures more efficient in real applications.

Restated for a non-expert reader; the original wording follows.

In the paper's words

Hierarchical (ultrametric) representations organize N items in a q-ary tree of depth n = lceil ln N / ln q rceil, and the branching factor q determines how storage, interconnection, and traversal resources scale. Prior ultrametric modeling has largely treated the radix as a fixed structural parameter inherited from the problem statement rather than as a design variable to be optimized. This paper treats q as the single decision variable in a constrained resource-allocation problem.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. We show analytically that the continuous optimum of $q/\ln q$ lies at $q = e \approx 2.718$, that the best integer radix at equal weights for $N = 10^6$ is $q = 4$, with $q = 3$ optimal only in the traversal-dominated regime where the traversal weight $\beta$ exceeds the derived threshold $\beta^{*} = 2.286$.

   from Abstract

2. Second, we evaluate the integer radices $q \in \{2,3,4,5\}$ with complete arithmetic for $N = 10^6$ and show that $q = 4$ is optimal at equal weights, with $q = 3$ becoming optimal only when the traversal weight exceeds the derived threshold $\beta^{*} = 2.286$.

   from 1. Introduction

3. Our sensitivity analysis in Section 4 plays the role of the ballistic-coefficient extrapolation: we fix a reference weighting and propagate its uncertainty into the design recommendation. [2] Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost (arXiv:1004.4609v1).

   from 2. Background and Related Work

4. The depth is $$n(q) = \left\lceil \frac{\ln N}{\ln q} \right\rceil.$$ We take the number of leaves as exactly $N$ (padding to a full $q$-ary tree with at most $q^n - N$ dummy leaves; the padding overhead is analyzed in Section 4.4).

   from 3.1 Setup

5. Padding overhead at $N = 10^6$: $4.86\%$ ($q=2$), $59.43\%$ ($q=3$), $4.86\%$ ($q=4$), $95.31\%$ ($q=5$); with padded storage the composite scores are $4.9928$, $5.2142$, $4.2937$, $5.6989$, and $q = 4$ remains optimal with a wider margin (Section 4.4).

   from 5. Results

6. Weight-sensitivity threshold: the $q=3$/$q=4$ optimum switch occurs at $\beta^* = 2.286$ (with $\alpha = 1$, unpadded storage); $q=2$ is dominated for all $\beta \gt 0$ (Section 4.5).

   from 5. Results

How it is done

1. We use this as the resource-ecosystem analogue of our problem: a large collection of resources whose access structure (the FAIR dimensions) must be balanced against curation and processing costs, with the assessment instrument playing the role of our resource functionals. [6] IVOA Recommendation: Resource Metadata for the Virtual Observatory Version 1.12 (arXiv:1110.0514v1).

   from 2. Background and Related Work

2. Let $N$ be the number of items to organize, and let the ultrametric representation be a rooted $q$-ary tree with all leaves at depth $n$.

   from 3.1 Setup

3. Following the three-resource taxonomy of [9], we define: Storage.

   from 3.2 Resource functionals

4. Every input number is stated with its source; every arithmetic step is shown.

   from 4. Analysis

What would falsify it

1. We situate the derivation within a synthesis literature that argues, in several adjacent fields, that optimization must respect cost metrics beyond the simplest count, and we state the falsification conditions under which the $q=3$ recommendation would fail.

   from Abstract

2. Our problem has the same shape in miniature: a handful of measured or assumed resource weights must be extrapolated into a design regime where the optimum is sensitive to them, and the honest deliverable is not a single number but a derivation with stated sensitivities and falsification conditions.

   from 1. Introduction

3. This inverts our problem — there the radix is unknown and must be recovered; here it is known and must be chosen — and the inversion is a useful check that our optimization is well-posed only when the radix is a genuine free parameter. [12] QNFO: The Trapped-Ion Ultrametric Testbed: A Falsifiability Register for Testing $p$-Adic Structure in Quantum Dynamics.

   from 2. Background and Related Work

Where the claim stops

1. The padding analysis assumes dummy leaves occupy real storage; in sparse implementations they may not, in which case the unpadded ranking (still $q=4$ at equal weights) applies.

   from 6. Discussion

2. Three falsifiers: (i) a measured workload class in which the effective per-level cost is superlinear in $q$, for which the $\beta^* = 2.286$ threshold would shift and could drop below 1, making $q = 2$ optimal after all; (ii) a workload $N$ for which the padded-storage ranking inverts in favor of $q = 3$, which would show that the $q = 4$ result is an artifact of the near-fit of $4^{10} = 1048576$ to $10^6$; (iii) an empirical demonstration that the traversal cost per level is well approximated by $q/\ln q$ even at small $q$, which would push the effective optimum toward $q = e$ and make $q = 3$ the integer winner at equal weights.

   from 6. Discussion

3. The continuous relaxation of the traversal term is minimized at $q = e \approx 2.718$, but the ceiling-quantized traversal term combined with the storage term shifts the integer optimum: for $N = 10^6$ at equal weights the optimum is $q = 4$ ($F_{1,1}(4) = 4.2289$), robust to padding, with $q = 3$ optimal only when the traversal weight exceeds $\beta^{*} = 2.286$ and $q = 2$ dominated by $q = 3$ for all $\beta \gt 0$.

   from 7. Conclusion

Where to read

1. Abstract275 words · 1 min
2. 1. Introduction425 words · 2 min
3. 2. Background and Related Work1,308 words · 6 min
4. 3. Methods376 words · 2 min
5. 4. Analysis919 words · 4 min
6. 5. Results209 words · 1 min
7. 6. Discussion375 words · 2 min
8. 7. Conclusion157 words · 1 min