Code to compute localization in SAGE of Z/nZ at a particular choice of multiplicative subset S = { s0^i }

localization-intuition-sage.py

import itertools
# check all pairs (a, c in R | b, d in S):
#      (a/b) ~ (c/d)
# check exists e in S: (ad - bc)e = 0

R = IntegerModRing(10)
S = []
s0 = R(6)

for i in range(0, 10000):
    if s0 ** i in S: break
    S.append(s0**i)

print("ring: %s" % R)
print("localizing at s0=%s | S = %s" % (s0, S))


equiv_relation = {}
for (a, b, c, d) in itertools.product(R, S, R, S):
    # break early, so we get that (a*d-b*c)*s = 0 for simpler s
    # [lower powers] than higher powers.
    for s in S:
        if (a * d - b * c) * s == R(0):
            equiv_relation[(a, b, c, d)] = s
            break

# for (a, b, c, d) in equiv_relation:
#     s = equiv_relation[(a, b, c, d)]
#     out = "%2s/%2s =%2s= %2s/%2s" % (a, b, s, c, d)
#     out += " [mod %s]" % (R.order())
#     out += "  |  "
#     out += "(%2s*%2s - %2s*%2s)%2s" % (a, d, b, c, s)
#     out += " = "
#     out += "(%2s - %2s) * %s" % (a*d, b*c, s)
#     out += " = "
#     out += "%2s * %2s" % (a*d - b*c, s)
#     out += " = %s" % ((a*d - b*c)*s)
#     print(out)

# compute equivalence classes
fracs = set(itertools.product(R, S))
equiv_classes = [] # (representative, set)

while fracs:
    # representative
    (a, b) = fracs.pop()
    cls = set([])
    cls.add((a, b))
    for (c, d) in fracs:
        for s in S:
            if s*(a*d - b*c) == 0:
                cls.add((c, d))
                break

    for frac in cls:
        if frac in fracs: fracs.remove(frac)

    # try to find a better representative that has denominator 1
    for (c, d) in cls:
        if d == 1:
            (a, b) = (c, d)
            break
    equiv_classes.append(((a, b), cls))

print("===Equivalence classes===")
for (rep, cls) in equiv_classes:
    print(rep, cls)

# check that all intersections are empty
for ((_, es), (_, fs)) in itertools.product(equiv_classes, equiv_classes):
    assert(es.intersection(fs) == es or es.intersection(fs) == set())

# check that the equivalence classes are exhaustive
for (r, s) in itertools.product(R, S):
    found = False
    for (_, cls) in equiv_classes:
        if (r, s) in cls: found = True
    if not found:
        raise RuntimeError ("element %2s/%2s not in any equivalence class" % (r, s))


# print how each representative relates to the other elements:

for ((a, b), cls) in equiv_classes:
    print("****%s/%s****" % (a,b))
    for (c, d) in cls:
        s = equiv_relation[(a, b, c, d)]
        out = "\t- %2s/%2s (~ %2s)" % (c, d, s)
        out += " [mod %s]" % (R.order())
        out += "  |  "
        out += "(%2s*%2s - %2s*%2s) * %2s" % (a, d, b, c, s)
        out += " = "
        out += "(%2s - %2s) * %s" % (a*d, b*c, s)
        out += " = "
        out += "%2s * %2s" % (a*d - b*c, s)
        out += " = %s" % ((a*d - b*c)*s)
        print(out)