This article presents an algorithmic research result developed by GPT-6-ASTRA. The complete code, formal proofs, benchmarks, and experimental results are available in the repository: ASTRA4OI.

Conclusions

The algorithm achieves a time complexity close to that of standard interval linear bases over fields. Let:

In particular, when m = p², each column requires only two slots, achieving the same dominant asymptotic complexity as a standard linear basis over a field. When k = 1, the algorithm reduces to a standard linear basis tracking latest positions.

This article introduces an interval linear representation algorithm under composite moduli.

Given a sequence of vectors:

the goal is to determine whether:

holds—that is, whether there exist coefficients $$$\lambda_i \pmod m$$$ such that:

The directory corresponding to this work is: composite-modulus-basis.

It includes:

• Full Proofs: SOLUTION.md
• Python Implementation: solver.py
• Independent Verification: test_solver.py
• Fixed-seed benchmarks and sample inputs/outputs

1. Why Standard Linear Bases Cannot Be Generalized Directly

Over a field, the core operation of a linear basis is using a pivot to eliminate entries in a column.

However, $$$\mathbb Z/m\mathbb Z$$$ is generally not a field when $$$m$$$ is composite: zero divisors exist, and non-zero elements may fail to be invertible.

For example, consider modulo $$$4$$$ with a single vector:

Standard Gaussian elimination would choose $$$a$$$ as the pivot for the first column. However, scalar multiplication yields:

which introduces new information in the second column.

If only one pivot is retained per column, the vector $$$(0,2)$$$ is lost.

Another challenge is that one cannot simply preserve the latest raw vector for each column.

Consider the 1D sequence modulo $$$4$$$:

The full interval $$$[1,2]$$$ can span $$$1$$$, whereas the sub-interval $$$[2,2]$$$ can only span $$$0$$$ and $$$2$$$.

Consequently:

• Keeping only the latest vector $$$2$$$ loses the span information of $$$[1,2]$$$.
• Keeping only the older vector $$$1$$$ fails to correctly reflect the suffix $$$[2,2]$$$.

Modulo $$$p^k$$$, the 1D sequence:

produces $$$k$$$ distinct suffix levels.

Therefore, under composite moduli, each column cannot hold merely a single pivot; it must maintain multiple $$$p$$$-adic levels.

2. The Prime Power Case: Modulo $$$p^k$$$

First, let:

where $$$p$$$ is a prime.

All coordinates are normalized to:

For a non-zero element $$$x$$$, define the $$$p$$$-adic valuation:

For example, modulo $$$8$$$:

For a non-zero vector $$$b$$$, let $$$j$$$ be the index of its first non-zero coordinate, and let:

Define its leading position as:

Leading positions are ordered lexicographically, comparing the coordinate index $$$j$$$ first, followed by the $$$p$$$-adic valuation $$$v$$$.

If the first non-zero entry of a vector is $$$p^v u$$$, where $$$\gcd(u, p) = 1$$$, multiplying the vector by the unit $$$u^{-1}$$$ normalizes the pivot to $$$p^v$$$.

Note that this only requires inverting units; non-units $$$p^v$$$ are never inverted.

3. The $$$p$$$-adic Echelon Table

We maintain a 2D table:

where:

• $$$j$$$ is the coordinate index;
• $$$v\in[0,k-1]$$$ is the $$$p$$$-adic level.

This yields $$$dk$$$ total slots.

Each slot stores a row tuple:

where:

• $$$b$$$ is the normalized vector;
• $$$t$$$ is the timestamp;
• $$$e$$$ indicates that the row originates from the $$$e$$$-th $$$p$$$-adic power level of the original vector $$$a_t$$$.

Rows in the table must satisfy:

1. The first $$$j$$$ coordinates are zero;
2. The coordinate at index $$$j$$$ is $$$p^v$$$;
3. The leading position of the row is $$$(j,v)$$$.

The timestamp signifies that this row was derived strictly from original vectors with indices $$$\ge t$$$.

Therefore, after processing up to the right endpoint $$$r$$$, answering queries for the interval $$$[l,r]$$$ requires considering only those slots whose timestamps satisfy:

4. The $$$p$$$-Digit Basis

The "basis" here is not a basis of a free module in the classical sense.

A set of rows is defined as a $$$p$$$-digit basis if every element in its span can be uniquely expressed as:

Each coefficient is restricted to a single base-$$$p$$$ digit.

Lemma 1: Uniqueness of Digit Combinations

Assume all rows possess distinct leading positions.

Consider a non-trivial linear combination:

Among all rows with $$$c_b \ne 0$$$, pick the row with the lexicographically minimal leading position, denoted $$$(j, v)$$$.

At column $$$j$$$:

• This row contributes $$$c_b p^v$$$;
• Any other row whose leading position is also at column $$$j$$$ has valuation at least $$$v+1$$$, contributing a term divisible by $$$p^{v+1}$$$;
• Rows whose leading positions fall on subsequent columns contribute zero at column $$$j$$$.

Since:

the term $$$c_b p^v$$$ is not divisible by $$$p^{v+1}$$$ and cannot be canceled by the other terms.

This yields a contradiction.

Hence, distinct $$$p$$$-digit combinations necessarily produce distinct vectors.

Lemma 2: Membership Queries via the Echelon Table

Assume the current table forms a $$$p$$$-digit basis for a submodule $$$H$$$.

Given a target vector $$$x$$$, process its non-zero coordinates from left to right.

If the current column $$$j$$$ has $$$p$$$-adic valuation $$$v$$$, query the slot:

If this slot is empty, $$$x \notin H$$$.

If the slot is occupied by pivot row $$$b$$$, compute:

Because $$$x_j$$$ and $$$p^v$$$ are standard integers with $$$p^v\mid x_j$$$, this requires exact integer division rather than modular inversion.

Update:

This completely clears column $$$j$$$.

Because every elimination clears the current leftmost non-zero entry, at most $$$d$$$ eliminations occur.

If $$$x$$$ reduces to the zero vector, a valid linear combination representing $$$x$$$ has been found.

Conversely, if a required slot is empty at any step, the uniqueness of the $$$p$$$-digit basis guarantees that $$$x$$$ cannot belong to $$$H$$$.

Thus, the membership query procedure is correct.

5. Dynamics of Inserting a New Vector

Suppose a submodule $$$H$$$ has already been established, and a new vector $$$a$$$ is inserted.

Consider the quotient group:

Because it is generated by $$$a+H$$$, it is a cyclic $$$p$$$-group.

Let its order be:

Then:

are all non-zero cosets, while:

Eliminating each of these vectors with respect to $$$H$$$ yields non-zero residual rows with strictly increasing leading positions, which can be written as:

where $$$u_e$$$ is an invertible unit.

Thus, inserting a vector introduces exactly $$$h$$$ new $$$p$$$-digit levels.

The number of digit combinations across these $$$h$$$ rows is:

which bijectively spans the cyclic quotient group:

Consequently:

If $$$H$$$ admits a $$$p$$$-digit basis, then upon inserting vector $$$a$$$, retaining the non-zero residuals of $$$a, pa, \ldots, p^{k-1}a$$$ modulo $$$H$$$ forms a valid $$$p$$$-digit basis for $$$H + Ra$$$.

This principle constitutes the core foundation of the algorithm.

6. The Timestamp Algorithm

Suppose we are inserting the $$$r$$$-th vector $$$a_r$$$.

We initialize a priority queue with up to $$$k$$$ tasks:

The queue enforces the following priority order:

1. Larger timestamps take precedence;
2. For identical timestamps, smaller power levels $$$e$$$ take precedence.

Each task also tracks a start column index indicating where to resume searching for pivots.

Pseudocode:

while queue is not empty:
    pop task (row, t, e, start) with the maximum timestamp

    find the first non-zero coordinate j of row starting from start
    if no such j exists:
        discard task
        continue

    v = valuation_p(row[j])
    old = B[j][v]

    if old does not exist:
        multiply row by unit inverse to normalize pivot to p^v
        B[j][v] = row
        terminate current task

    if old.timestamp > t:
        eliminate column j of row using old
        continue processing row from j + 1

    if t > old.timestamp:
        normalize row and replace old with row
        eliminate old using the new row
        re-insert residual of old into queue with its original timestamp
        terminate current task

Distinct power levels sharing the same timestamp will never collide on the same slot, as guaranteed by the cyclic quotient group lemma above.

A replaced row must re-enter the queue rather than continuing elimination inline. All newer timestamps must stabilize first so that older rows can be eliminated with respect to the updated, newer submodule.

7. Proof of Correctness

Let:

After processing the prefix $$$a_1,\ldots,a_r$$$, the following invariants are maintained:

Invariant 1

For any left endpoint $$$l$$$, the set of all table rows with timestamp $$$t \ge l$$$ constitutes a $$$p$$$-digit basis for the submodule generated by the interval:

Invariant 2

Let the order of $$$a_t$$$ in the quotient group:

be:

Then there are exactly $$$h_t$$$ rows in the table with timestamp equal to $$$t$$$, corresponding to power levels:

Furthermore, each such row satisfies:

where $$$u_{t,e}$$$ is a unit.

Inductive Proof

When the table is empty, the invariants trivially hold.

Assume by induction that after inserting a new vector, all rows with timestamps strictly greater than $$$t$$$ have stabilized.

These rows generate the updated suffix submodule:

Now consider rows with timestamp $$$t$$$.

Prior to the insertion, rows at timestamp $$$t$$$ corresponded to levels in the older quotient group.

Adding newer vectors enlarges $$$H$$$, which can only decrease or maintain the order of elements in the quotient group.

If the updated order exponent is $$$h_{\text{new}}$$$ and the prior exponent was $$$h_{\text{old}}$$$, then:

For power levels $$$e \ge h_{\text{new}}$$$:

meaning these levels will ultimately be eliminated completely by newer rows.

For $$$e \lt h_{\text{new}}$$$, the corresponding cosets remain non-zero and will settle at a leading position currently vacant in $$$H$$$.

If that position previously held a row with an older timestamp, the newer row preempts it, and the residual of the older row is re-queued.

Because the priority queue always prioritizes newer timestamps, all tasks at timestamp $$$t$$$ stabilize before any older tasks are processed.

By the cyclic quotient group lemma, timestamp $$$t$$$ retains exactly the levels:

each occupying distinct leading positions.

Hence, Invariant 2 holds for timestamp $$$t$$$.

Inducting downward from newer to older timestamps establishes the invariants across the entire table.

Consequently, after processing up to right endpoint $$$r$$$, filtering rows with timestamp $$$\ge l$$$ yields an exact $$$p$$$-digit basis for the interval $$$[l,r]$$$.

By Lemma 2, the query returns YES if and only if:

The algorithm is therefore correct.

8. Complexity Analysis

Each insertion initially introduces at most $$$k$$$ power chains.

Each elimination step in a task clears one coordinate and advances to the next column; thus, a single chain visits at most $$$d$$$ columns.

Visiting each column entails a vector operation of length $$$d$$$, taking $$$O(d)$$$ time.

Therefore, the dominant complexity of a single vector insertion is:

Processing all $$$n$$$ vectors requires:

A single query clears at most $$$d$$$ coordinates, with each elimination taking $$$O(d)$$$ operations:

Summary for modulo $$$p^k$$$:

Additional secondary costs include:

• Priority queue operations;
• $$$p$$$-adic valuation evaluations;
• Inversion of units;
• Big-integer arithmetic overhead.

These depend on the bit-length of $$$p^k$$$.

9. Generalization to Arbitrary Composite Moduli

Let:

where the $$$p_s$$$ are pairwise distinct primes.

By the Chinese Remainder Theorem (CRT):

Thus, a vector is representable modulo $$$m$$$ if and only if it is representable across every prime-power component independently.

The overall procedure is:

1. Construct an independent $$$p$$$-adic echelon table for each prime-power component $$$p_s^{k_s}$$$;
2. Query each component independently on the given interval;
3. Return YES if and only if all components return YES.

A key algebraic property guarantees sufficiency:

The linear coefficients recovered in distinct prime-power components may differ:

However, for each fixed index $$$i$$$, these independent coefficients $$$\lambda_i^{(s)}$$$ can be combined via CRT into a unified coefficient $$$\lambda_i \pmod m$$$.

Hence, individual components are not required to yield identical linear coefficients prior to combination.

Let:

The overall complexities are:

for preprocessing, and:

per query.

When maintaining persistent prefix snapshots for online queries, the space complexity is:

For offline processing ordered by right endpoint, the working basis space is:

Integer factorization is not factored into the asymptotic bounds above.

The implementation falls back to trial division by default; large moduli should have their prime factorizations supplied explicitly via the --factors flag.

10. Online vs. Offline Variants

Offline Variant

Queries are bucketed by right endpoint $$$r$$$.

Vectors are processed left-to-right:

for r = 1 .. n:
    insert a_r
    answer all queries with right endpoint r

This mode only requires storing the single active echelon table.

Online Variant

To query arbitrary historical intervals while vectors are dynamically appended, a table snapshot is recorded after each append.

Because snapshots copy only slot references and row objects are immutable:

• Each snapshot performs $$$O(dk)$$$ reference copies;
• Total persistent space across all prefixes is $$$O(nd^2k)$$$;
• Query complexity remains $$$O(d^2)$$$.

The current implementation supports:

• Appending new vectors;
• Querying arbitrary historical intervals;
• Computing submodule orders (sizes).

Mutations or deletions of intermediate vectors are not supported.

11. Implementation and Verification

The repository implementation relies exclusively on the Python standard library:

solver.py

Testing uses independent brute-force submodule generation as the ground truth reference, ensuring that the algorithm under test never generates its own validation targets.

The current test suite covers:

• Exhaustive verification for moduli $$$4, 8, 2, 6, 12$$$;
• Randomized stress tests for moduli $$$4, 5, 6, 8, 9, 12, 18$$$;
• Negative coordinates and inputs exceeding the modulus;
• Zero vectors;
• Online historical queries;
• Offline queries;
• Submodule size computations;
• Invariant assertions on timestamps and power levels;
• Cross-validation against explicit closure algorithms;
• Reductions on finite commutative rings.

Empirical verification scope includes:

• 9,278 sequences;
• 79,694 intervals;
• 5,959,998 membership assertions;
• 153,600 finite ring reduction assertions.

Execution commands:

cd results/composite-modulus-basis

python3 test_solver.py
python3 solver.py < example.in
python3 solver.py --online < example.in
python3 solver.py --factors 2:2 < example.in

12. Scope and Limitations

This work primarily addresses interval submodule membership queries over:

Key caveats:

1. Factorization costs for composite $$$m$$$ must be accounted for separately;
2. Bases provided via --factors must be verified primes;
3. The general finite commutative ring extension provides theoretical reductions, not an arbitrary ring input interface;
4. The online version supports append and historical queries, but not point updates or deletions;
5. Modular operation counts must be scaled by big-integer bit complexities when working with large numbers.

Summary

Linear algebra over composite moduli exhibits fundamental differences compared to linear algebra over fields:

• Non-unit elements cannot be inverted directly;
• Zero divisors generate non-trivial cascading pivots;
• A single timestamp may need to retain multiple $$$p$$$-adic power levels;
• The standard strategy of retaining one latest pivot per column fails.

The resolution consists of:

1. Allocating multiple $$$p$$$-adic slots per column for modulo $$$p^k$$$;
2. Characterizing finitely generated submodules via $$$p$$$-digit bases;
3. Tracking timestamps to maintain all suffixes simultaneously;
4. Enforcing strict queue ordering to guarantee proper elimination between newer and older rows;
5. Applying the Chinese Remainder Theorem to generalize to arbitrary integer moduli.

Full repository and assets:

https://github.com/Zi-Gao/ASTRA4OI

This article and the underlying algorithmic results were produced by GPT-6-ASTRA.