\
# Independent Reimplementation Guide

## 1. Purpose and conformance target

This document specifies the mathematical pipeline implemented by `alexander-grobner` 0.4.1 closely enough for an English-speaking reader to build an independent implementation in Python, SageMath, Singular, Macaulay2, or another exact computer-algebra system.

A conforming implementation should, for the bundled inputs, produce the same reduced Gröbner bases over `QQ` with lexicographic order `t1 > ... > tell`. It need not reproduce the package’s JSON metadata, timing fields, or optimization choices exactly.

## 2. Fixed conventions

Let

```text
G = <x1,...,xn | r1,...,rm>
```

be a finite presentation and let `phi:G -> Z^ell` be an epimorphism. Write

```text
Lambda = QQ[t1^±1,...,tell^±1]
P      = QQ[t1,...,tell].
```

The abelianized Fox matrix `A` has relators as rows and generators as columns:

```text
A[i,j] = Phi(partial r_i / partial x_j).
```

The relative Alexander module and elementary ideals use the convention

```text
A_rel(G,phi) = Coker(A.T)
E_k(G,phi)   = Fitt_k(A_rel(G,phi)) = I_{n-k}(A).
```

Thus `n` is the number of columns of `A`, not the number of rows. Use

```text
I_r = (1)  for r <= 0,
I_r = (0)  for r > min(number_of_rows, number_of_columns).
```

The final Alexander–Gröbner invariant is the reduced Gröbner basis of `E_k intersect P` in lexicographic order

```text
t1 > t2 > ... > tell.
```

## 3. Input validation

For a finite-presentation input:

1. generator indices in relators are signed, one-based integers;
2. the image of every relator in `Z^ell` must be zero;
3. the generator images must span the target lattice, not merely the target vector space over `QQ`;
4. variable names must be distinct;
5. unknown top-level fields should be rejected rather than silently ignored.

To test surjectivity onto the lattice, compute the greatest common divisor of all `ell x ell` minors of the integer matrix of generator images. The map is onto precisely when that gcd is `1`.

For PD input, computed provenance fields—such as crossing signs, Wirtinger arcs, component data, and the normalized PD code—must not be overwriteable by user-supplied metadata.

## 4. Knot Atlas-style oriented PD codes

A crossing `X_{i,j,k,l}` is read from the incoming lower edge counterclockwise. The edge labels increase along each oriented component.

Validation requirements:

- for `c` crossings, labels are exactly `1,...,2c`;
- every label occurs exactly twice;
- `(i,k)` are the two lower-strand labels and `(j,l)` the two upper-strand labels;
- the orientation encoded by the labels must be consistent at every crossing.

Partition edge labels into components by joining `(i,k)` and `(j,l)` at each crossing. Partition them into Wirtinger arcs by joining the two upper labels `(j,l)` at each crossing. By default, order components by their smallest edge label; allow an explicit component permutation.

At a crossing, let `incoming`, `outgoing`, and `over` be the one-based Wirtinger-generator indices. With the sign convention used by the package, insert

```text
positive crossing:  over^-1 * incoming * over * outgoing^-1
negative crossing:  over    * incoming * over^-1 * outgoing^-1.
```

If the projection graph is connected, one Wirtinger relation may be dropped. For a disconnected projection graph, retain all crossing relations.

Each Wirtinger generator maps to the standard basis vector associated with its component.

## 5. Abelianized Fox calculus

Represent a relator as a signed word. Let `M_j` be the Laurent monomial image of generator `x_j` under `phi`. Traverse each relator from left to right while maintaining the abelianized prefix `p`.

For a positive letter `x_j`:

```text
row[j] += p
p       *= M_j
```

For a negative letter `x_j^-1`:

```text
row[j] -= p / M_j
p       /= M_j
```

At the end of a relator, `p` must equal `1`. This implements the Fox rules after abelianization without constructing noncommutative group-ring expressions.

For every row, verify the abelianized Fox fundamental identity

```text
sum_j A[i,j] * (M_j - 1) = 0.
```

## 6. Clear Laurent exponents correctly

Do **not** multiply matrix entries independently by unrelated Laurent monomials. That operation need not preserve higher determinantal ideals.

For each row, find the minimum exponent of every variable among all monomials occurring in all entries of that row. Multiply the entire row by the smallest Laurent monomial that makes all exponents nonnegative.

A minor using a set of rows is then multiplied by the product of the corresponding row units. Since those factors are units in `Lambda`, the Laurent determinantal ideal is unchanged.

## 7. Form the Fitting ideal

Set

```text
r = n - k.
```

Enumerate all `r x r` minors of the polynomialized matrix. Discard zero minors. Over `QQ`, each nonzero generator may be made monic without changing the ideal.

The number of candidate minors is

```text
binomial(rows,r) * binomial(columns,r).
```

A practical implementation should inspect this number before enumeration and impose a configurable safety limit.

## 8. Contract the Laurent ideal to the polynomial ring

Let `J` be the polynomial ideal generated by the polynomialized minors and set

```text
T = t1 * ... * tell.
```

The desired contraction is

```text
(J Lambda) intersect P = J:T^infinity.
```

Compute it by introducing an auxiliary variable `z` and eliminating `z` from

```text
J + (1 - z*T)
```

with lexicographic order

```text
z > t1 > ... > tell.
```

The polynomials in the resulting Gröbner basis that do not involve `z` generate the saturation in `P`.

An optional pre-reduction of `J` by a Gröbner basis in a faster order such as grevlex may reduce the number and size of generators before saturation. It is an optimization only and must not change the final ideal.

## 9. Canonical final output

Recompute the saturated ideal’s reduced Gröbner basis over `QQ` in lexicographic order

```text
t1 > ... > tell.
```

Return the expanded monic polynomials in the canonical order supplied by the CAS. A factored display may be added separately, but the expanded reduced basis is the canonical result used for comparison.

For the zero ideal, use the empty basis. For the unit ideal, use `{1}`.

## 10. Normalized common divisor

When a common divisor is reported, compute the polynomial gcd of the basis elements over `QQ`, remove any common monomial factor, and make the result monic. This treats nonzero rational scalars and Laurent monomials as units.

Consequently, an integral representative containing a factor such as `2` may be displayed without that factor in the program’s `QQ`-normalized output.

## 11. Verification tests

At minimum, an independent implementation should test:

1. the Fox fundamental identity row by row;
2. the trefoil from several presentations, obtaining `t1^2-t1+1` for `AG_1`;
3. the Hopf link from a PD code and from a commutator presentation, obtaining `{t1-1,t2-1}` for `AG_1`;
4. invariance under a simple Tietze expansion;
5. equivalence of product saturation and successive saturation by each variable;
6. stability of the final basis under a fresh reduced-lex computation;
7. monicity, reducedness, and Buchberger’s criterion;
8. all bundled Section 3 regression cases.

A stronger audit should recompute representative cases in a second CAS.

## 12. Reference pseudocode

```text
function compute_AG(presentation, k):
    validate_presentation_and_epimorphism(presentation)
    variables, A = abelianized_fox_matrix(presentation)
    assert fox_fundamental_identity(A)

    B = clear_negative_exponents_row_by_row(A)
    r = number_of_columns(B) - k
    minors = all_nonzero_r_by_r_minors(B, r)

    J = ideal(minors) in QQ[t1,...,tell]
    T = product(t1,...,tell)
    K = eliminate_z( J + ideal(1-z*T), order=z>t1>...>tell )

    return reduced_groebner_basis(K, order=t1>...>tell)
```

## 13. Source-code map

The reference implementation is organized as follows:

- `model.py`: validated presentation and lattice-surjectivity check;
- `io.py`: JSON input, strict field checking, and source-file hashes;
- `pd.py`: PD parsing, orientation analysis, component/arc partition, and Wirtinger presentation;
- `fox.py`: abelianized Fox matrix, Fox identity, and row-wise denominator clearing;
- `ideals.py`: minor enumeration, saturation, reduced bases, gcd normalization, and independent basis checks;
- `compute.py`: end-to-end pipeline and result record;
- `reproduce.py`: frozen Section 3 cases and regression comparison;
- `formatting.py`: text, JSON, and LaTeX output;
- `cli.py`: command-line interface.

## 14. Scope

This specification covers the exact algebraic pipeline used for the bundled computations. It does not certify that an external database label names the archived PD code, decide link equivalence, or specify an exhaustive link-table crawler.