Sublinear Membership Testing in Two-Generator Matrix Groups

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Subgroup membership asks whether an input matrix is a finite word in the two displayed generators and their inverses. The matrices have determinant one, so their products lie in $\mathrm{SL}(2,\mathbb Q)$.

The group $\mathrm{GL}_n(\mathbb Z)$ consists of integer matrices with integer inverses, and $\mathrm{SL}_n$ imposes determinant one. The subgroup generated by matrices consists of finite products of them and their inverses. A centralizer consists of elements commuting with the specified element.

Statement recorded in the supplied source.

For an integer $K\geq2$, let $H(K)\leq\operatorname{SL}(2,\mathbb Q)$ be generated by

$$A(K)=\begin{pmatrix}1&K\\0&1\end{pmatrix},\qquad B(K)=\begin{pmatrix}1&0\\K&1\end{pmatrix}.$$

Is there a sublinear-time algorithm for the subgroup membership problem in $H(K)$? [S2]

Scope qualification.

The input length, access model, and meaning of sublinear are not specified; reading an explicitly encoded matrix is a separate cost.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Decide membership in the explicit two-generator matrix group in sublinear time.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003187 (OWR-14745-006). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Computational Group Theory $2017$, Oberwolfach Reports, DOI 10.4171/owr/2016/37, pp. 2123--2169 https://doi.org/10.4171/owr/2016/37.
• S3 Chorna--Geller--Shpilrain https://arxiv.org/abs/1605.05226. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003187 and source code OWR-14745-006 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The original problem-session passage in OWR 37/2016, p. 2163, was read in the cached primary report. It asks about integer $K\ge2$ but supplies no encoding or cost convention. The abstract of Chorna--Geller--Shpilrain, arXiv:1605.05226v4, was also consulted; it concerns membership and its complexity, but its full theorems were not inspected here. The following elementary argument is a restricted access-model result, not a claimed new answer to that paper or to all interpretations of sublinear time.

Research attempt: A bit-query obstruction on upper unipotent inputs

Exact intersection calculation.

Fix an integer $K\ge2$, and put $U(M)=\left(\begin{smallmatrix}1&M\\0&1\end{smallmatrix}\right)$ for an integer $M$. Then \[ U(M)\in H(K)\quad\Longleftrightarrow\quad K\mid M. \] The reverse implication is $U(M)=A(K)^{M/K}$. For the forward direction, combine adjacent powers of the same generator and remove powers with exponent zero in any representing word. Apply the resulting alternating word to $e_1=(1,0)^T$, from right to left. A rightmost power of $A$ fixes $e_1$ and can be discarded for this calculation. If any $B$ remains, its first application gives $(1,bK)^T$, with $b\ne0$, so $|y|>|x|$ and $y\ne0$. Whenever $|y|>|x|$, a nonzero power $A^a$ gives \[ |x+aKy|\ge K|y|-|x|>|y|. \] Whenever $|x|>|y|$, a nonzero power $B^b$ similarly gives $|y+bKx|>|x|$. Thus after the first $B$, the second coordinate never vanishes: an $A$ step preserves it and a $B$ step makes its absolute value strictly positive. A word containing $B$ therefore cannot be upper triangular. A word without $B$ is $A^a$, proving the assertion without invoking a freeness theorem.

Linear input-bit lower bound.

Take the fixed value $K=3$, or any fixed odd $K\ge3$. The input is an explicitly encoded integer matrix, with random access to individual binary digits; exact membership must be correct on every valid input. For $L\ge1$, let \[ M_0=K2^L,\qquad M_i=K2^L+2^i\quad(0\le i<L). \] All matrices $U(M_i)$ have determinant one and the same bit length. Their encodings differ from $U(M_0)$ in exactly one of its bottom $L$ digits. The base matrix belongs to $H(K)$, and none of the alternatives does, since odd $K>1$ cannot divide $2^i$.

On the base input a deterministic exact algorithm must inspect all these $L$ digits. If it omits digit $i$, its entire adaptive transcript is identical on the corresponding alternative, yet the required answers differ. The total input length is $\Theta(L)$, so even this promised subclass precludes a worst-case sublinear bit-query bound.

The conclusion also holds for bounded-error randomization with a worst-case cap of $q$ bit queries. Give the base input probability $1/2$ and distribute the other probability $1/2$ uniformly over the $L$ alternatives. Couple the algorithm's random coins on the base and a random alternative. Until the changed digit is inspected, the two executions coincide. On the base path at most $q$ of the $L$ positions are inspected; consequently the probability of seeing the change is at most $q/L$. The resulting transcript distributions have total variation at most $q/L$: the probability of a differing coupled transcript bounds the difference of probabilities of every event. Under equal priors, any decision rule therefore has average error at least $(1-q/L)/2$, since its acceptance probabilities differ by at most $q/L$. Worst-case error at most $1/3$ forces $q\ge L/3$.

Why this does not settle the unqualified question.

The obstruction charges access to digits, not arithmetic operations on an already loaded integer, and concerns worst-case exact or bounded-error correctness, not generic-case rejection. It does not rule out a sublinear bound in the numerical magnitude $\max |M_{ij}|$, a promise excluding these inputs, or a word-RAM convention making long-integer operations free. For $K=2$ this particular upper-unipotent restriction merely tests parity and has a one-bit algorithm; extending the obstruction to every $K$ would require a different family. The source supplies none of the conventions needed to identify these variants.

Verification and adversarial audit

The alternating-word argument was checked for the empty word, a pure $A$ power, negative exponents, $K=2$, and a word beginning or ending with either generator. Strict dominance, rather than positive entries, is what handles cancellation. All adversarial inputs are integral determinant-one matrices with equal encoding lengths. The randomized argument uses a distribution on valid matrices and explicitly states its worst-case query cap; it is not an unexplained appeal to an information bound.

Audit corrections.

Rejected an unproved congruence-only characterization of the entire subgroup. The proof instead establishes only the upper-unipotent intersection and keeps the $K=2$ boundary and encoding dependence explicit.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The proved lower bound is complete for the stated bit-query promise subclass with fixed odd $K\ge3$. The original access model, cost parameter, all-$K$ interpretation, and possible generic-case algorithms remain unspecified or untreated. No full-source resolution or novelty claim is made.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46642 (consulted 2026-10-11).
• https://arxiv.org/abs/1605.05226 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written-proof review of this attempt; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.