Source-linked AI summary
Deterministic Linear-Time Modular Subset Sum
Phuoc Dinh Le, Kha Le
TL;DR
Exact modular subset sum asks which residues are reachable using input copies, each at most once. The paper uses run-based cycle updates to solve the compact-input problem deterministically in linear time, improving the prior deterministic bound while matching the cost of reporting all residues.
Problem
For compact input, exact modular subset sum asks which residues are reachable from distinct input residues with given multiplicities, a problem previously having a deterministic O(m log m α(m)) bound.
Source: §1 · p. 1Method
The algorithm stores reachable residues as runs along cycles, groups updates by gcd class, grows the modulus through increasing prime factors, and radix-sorts boundary batches.
Source: §1 · p. 2, §5.1 · p. 14Results
O(m) time and O(m) auxiliary words suffice to report all reachable residues and answer one target query with a witness when reachable.
Source: §1 · p. 1Takeaways & Limitations
The linear running time matches the cost of explicitly reporting all m reachability bits.
Source: §1 · p. 1The stated guarantee assumes compact input and an arithmetic word-RAM with constant-time operations including quotient, remainder, and modular multiplication.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$. The input gives distinct residues and their multiplicities. The algorithm reports all reachable residues and answers one target query. It returns a witness when the target is reachable. The algorithm uses $O(m)$ auxiliary words on an arithmetic word-RAM. This improves Pot\k{e}pa's deterministic $O(m\log m\,\alpha(m))$-time bound under the same input convention. The running time matches the cost of explicitly reporting all $m$ reachability bits. We represent reachable residues as runs along cycles of repeated addition. Newly reached residues pay for scans of partial runs. We process prime factors in increasing order so that cycle rebuilding takes linear time. A theorem on subset sums of distinct units limits the number of adaptive boundary batches to $O(m^{3/4})$. Radix sorting their $O(m)$ total keys also takes $O(m)$ time.
1 Introduction and main result
The paper gives a deterministic O(m)-time, O(m)-space algorithm for exact modular subset sum on compact input, returning all reachable residues and supporting one target query with a witness. Its run-based updates, ordered modulus growth, and bounded boundary sorting yield linear total work.
1 Introduction and main result
- The O(m) bound improves Potępa’s deterministic O(m log m α(m)) bound under the same compact-input convention and matches the cost of reporting all m reachability bits.The compact input has at most m distinct-residue records, each paired with a multiplicity.Source: §1 · p. 1
- For every modulus, the algorithm deterministically reports all reachable residues in O(m) time and O(m) auxiliary words, and answers one target query with a witness when reachable.The explicit-list corollary gives O(n+m) time and O(m) auxiliary space for n reduced residues scanned twice, including a witness using distinct original indices.Source: §1 · p. 1
- Across benchmark inputs, median runtimes are about 5.5–33× faster than the hashed shift tree and 19–135× faster than the deterministic shift tree.The authors identify this as the first deterministic O(m)-time algorithm for unrestricted exact modular subset sum on compact input over arbitrary moduli.Source: §1 · p. 2
- The stated model is an arithmetic word-RAM with constant-time arithmetic operations, including quotient, remainder, and modular multiplication.Nonzero multiplicities are capped at min{cx, m/gcd(x,m)−1}; zero records are discarded.Source: §1 · p. 2
- Run scans cost O(m) in total because each update’s partial runs are bounded by newly reached residues; increasing-prime-factor modulus growth also keeps cycle rebuilding linear.Values are grouped by gcd with m and processed consecutively as the working modulus grows from 1 to m.Source: §1 · p. 2
- A distinct-unit subset-sum theorem limits adaptive boundary batches, allowing radix sorting of O(m) total boundary points in O(m) time.The remaining values in a gcd group can be skipped once enough distinct values fill its nonempty cycles.Source: §1 · p. 2
2 The core algorithm: one cycle
The algorithm represents reachable residues as runs in a cyclic ordering where adding the current direction advances one position. It changes direction by reconstructing run boundaries, then extends and merges runs to implement each subset-sum update.
2 The core algorithm: one cycle
- In a prime modulus, a nonzero direction orders every residue cyclically, and reachable positions are stored as maximal runs in an interval list.Position t represents td mod p; a run’s endpoints are positions, and a full cycle is represented by a flag.Source: §2 · p. 3
2.1 Change direction from d to x
- Changing direction from d to x preserves membership while sorting boundary events in the new cycle order to reconstruct the same reachable runs.The boundary sets are P = S \ (S + x) and Q = (S + x) \ S, with equal size δ; reconstruction costs O(1 + r_d(S) + δ) plus sorting 2δ keys.Source: §2.1 · pp. 4–5
2.2 Extend and merge the runs
- In the new direction, extending each run by one adds exactly Q and merging touching runs produces S′ = S ∪ (S + x).The update takes O(1 + r_x(S) + δ) time in the existing order and records a parent for each newly reached residue.Source: §2.2 · p. 5
- Processing copies of each value consecutively avoids repeated direction changes, so boundaries are sorted at most once per distinct input value.Once the cycle is full, further copies are not processed; all prime-case work outside boundary sorting is O(p), and sorting is also O(p) overall.Source: §2.2 · p. 6
3 Arbitrary moduli: several cycles
For arbitrary moduli, the algorithm represents reachable residues as runs within cycles determined by the current direction. It finds membership boundaries, rebuilds the representation when needed, then extends and merges runs to incorporate each input copy.
3 Arbitrary moduli: several cycles
- For arbitrary moduli, residues are partitioned into cycles for the current direction, and each cycle stores its reachable positions as maximal runs or as FULL/EMPTY.Adding the direction advances one position within each cycle, so the one-cycle update applies independently to each cycle.Source: §3 · p. 6
- In the modulo-12 example, changing direction from 4 to 3 represents the same reachable set as three partial cycles instead of one full cycle.The set is {0, 4, 8}.Source: Figure 2 · p. 7, §3 · p. 7
3.1 Find boundaries before rebuilding
- Boundary sweeps compare the reachable set with its shift, scanning partial cycles and enumerating membership changes in O(1 + Rd(S) + δ) when gcds match, or O(g + Rd(S) + δ) otherwise.When gcds differ, each partial list is scanned at most twice while visiting g cycles.Source: §3.1 · pp. 7–8
3.2 Rebuild from the boundaries
- Sorted START/END events rebuild the unchanged set in the new direction; cycles without events are classified FULL or EMPTY from membership bits.At a gcd change, rebuilding costs O(g + h + δ); with equal gcds, rebuilding partial cycles costs O(δ).Source: §3.2 · p. 8
3.3 Extend and merge the runs
- Extending each partial run by one and merging touching runs computes S ∪ (S + x), preserves exact membership and valid parents, and leaves at most δ partial runs.The extension itself costs O(1 + Rx(S) + δ) and requires no sorting.Source: §3.3 · p. 9
4 Choosing the input order
The algorithm orders inputs by gcd class and processes them along working moduli that grow through prime factors. This ordering makes cycle rebuilding linear in total, while the update analysis bounds scans and boundary work.
4 Choosing the input order
- Grouping residues by gcd and processing them along successively larger subgroups makes all cycle rebuilding take O(m) time in total.Rebuilding at a gcd change costs O(g + h), and reordering preserves the final subset sums.Source: §4 · p. 10
4.1 Working moduli and input order
- The working modulus starts at 1 and grows by multiplying prime factors in increasing order; each input residue is processed when its scale divides it.The embedding into a larger working modulus preserves every represented original residue.Source: §4.1 · p. 10
- Records are grouped by their original gcd with m, and each gcd class is processed consecutively at its eligible stage.Records in a class share the same first eligible working modulus.Source: §4.1 · pp. 10–11
4.2 Total cost of scans and rebuilding
- Stage rebuilding costs O(m) in total, and gcd changes also cost O(m) under the increasing-prime order.Each stage costs O(aiσ(Ai)); summing across prime stages yields the linear bound.Source: §4.2 · p. 12
- Across updates, at most 2(m − 1) keys are sorted, while loop checks, interval scans, boundary enumeration, merging, and parent recording take O(m) total time.The analysis also bounds partial-run scans by the number of newly reached residues.Source: §4.2 · pp. 12–13
5 Linear total sorting time
A completeness theorem bounds the number of boundary-sorting batches, and radix sorting makes their total cost linear. The bound follows because enough distinct units fill every initially nonempty cycle.
5.1 Bounding the number of sorting batches
- For a nonzero-residue class with L = m/g ≥ 2, distinct records give distinct units modulo L; when their subset sums cover ZL, every entry-nonempty cycle becomes full and the phase’s remainder is skipped.Source: §5.1 · p. 13
- O(m^3/4) bounds the number of nonempty batches requiring sorting.Only changes of direction require sorting; each batch is a list of boundary events.Source: §5.1 · pp. 13–14
5.2 Radix sorting every batch
- Stable LSD radix sort handles keys in [0, m) in at most eight passes.Each batch costs O(k + D), including counter resets.Source: §5.2 · p. 14
- O(m) deterministic time and O(m) auxiliary words suffice to sort all batches, including initialization and counter resets.The proof combines O(m) total keys with O(m^3/4) batches.Source: §5.2 · p. 14
6 Preprocessing
Preprocessing caps redundant multiplicities, builds gcd and inverse tables, and assigns records to stages. These steps take O(m) time and auxiliary words.
6 Preprocessing
- Replacing each nonzero record’s count by min{cx, m/gcd(x,m)−1} preserves all subset sums, and zero records can be discarded.A chosen count can be reduced modulo the additive order m/gcd(x,m).Source: §6 · p. 15
- O(m) word operations and auxiliary words compute every nonzero residue’s gcd with m and the required coordinate inverses without given factorization.A linear sieve supplies smallest prime factors, and prefix products recover inverses with one Euclidean inversion per gcd class.Source: §6 · p. 15
- The inverse computation costs O(k + log L) per nonempty gcd class, with total cost expressed as Σ_g k_g + |G| log(m + 1).The resulting prefix products and residue-indexed tables occupy O(m) words.Source: §6 · p. 15
- Factoring m, assigning stages, and grouping records take O(m) time and auxiliary words.The working modulus grows by prime factors from 1 to m, and the stage scan is bounded by the number of gcd classes.Source: §6 · p. 16
7 Witness reconstruction and total complexity
The algorithm reconstructs a target witness by following first-discovery parents, while the theorem proof combines the exact reachable-set computation with preprocessing and sorting bounds. The resulting guarantees include compact and explicit-list inputs.
7 Witness reconstruction and total complexity
- Any target is either reported unreachable or given a witness using at most m −1 distinct input copies, reconstructed in O(m) time and auxiliary words.Following parent records from the target to zero yields counts within each record’s available multiplicity.Source: §7 · p. 16
- The proof establishes that capping, embeddings, exact updates, and skipped copies preserve the full reachable set, while parent records provide the witness guarantee.The theorem’s components each take O(m) time, and peak auxiliary space is O(m) words.Source: §7 · p. 16
- For an explicit list of n reduced residues, time is O(n+m) and auxiliary space is O(m), excluding original input storage.A requested witness uses distinct original list indices.Source: §7 · p. 16
8 Implementation and experiments
Benchmarks compare bitset DP and two shift-tree algorithms across three input families and prime or composite moduli. The linear algorithm is faster than both shift trees across the plotted inputs, while bitset DP leads on two families.
8 Implementation and experiments
- Validation checks full reachable sets on 3,883 inputs, replays growth updates against Bellman’s recurrence, queries every target, and verifies returned witnesses.The inputs include exhaustive small multiplicity vectors, targeted cases, and seeded random cases.Source: §8 · p. 17
- The benchmarks use five size anchors, each with a prime and a composite modulus, and generate random-support, repeated-generator, and powers-of-three inputs.All four solvers receive the same 30 fixed inputs; each has one warm-up and three timed runs per input.Source: §8 · p. 17
- Bitset DP is faster on random support and powers of three, while repeated generators require m−1 full-bitset scans taking Θ(m^2/w) time.The algorithm’s runtime grows roughly linearly with m over the plotted range in Figure 3.Source: §8 · p. 17, Figure 3 · p. 18
- About 5.5–33× speedups over the hashed shift tree and 19–135× over the deterministic shift tree were observed across 30 plotted inputs.Figure 4 shows all algorithms in seconds, with separate vertical scales for each input family and rows for prime and composite moduli.Source: §8 · p. 17, Figure 4 · p. 18