Help with SAGE/python: removing elements from a list with respect to an equivalence relation

Question

I'm not entirely sure if this is the right forum for this but here goes: Let $l$ be a prime and let $p\equiv 1 (\text{mod} \ l)$ be prime as well. Let $\zeta \in \mathbb{Z}$ be a primitive $l$-th root of unity modulo $p$. I have a list of integers, call it $B$. I will call two numbers $a,b$ from $B$ equivalent if $a \equiv \zeta^kb \ (\text{mod} \ p)$ for some $k=0,...,l-1$. I would like to create a new list $A$ containing one and only one element from the equivalence classes of $B$. For example if $l=5,p=31, \zeta=2$ and $B=\{3,4,17\}$, then $A=\{3,4\}$ since $3 \not \equiv 2^k4 \ (\text{mod} \ 31)$ for all $k$ and $3 \equiv 2^117 \ (\text{mod} \ 31)$. I have a very limited understanding of coding. I know that I probably need to create a list $A$ containing the first element of $B$ and then do a for loop running through the elements $B[i]$ of $B$, then within that loop, run through the elements $a$ of $A$ and if $B[i]\not \equiv \zeta^ka \ (\text{mod} \ p)$ for all $k$, then $A.append(B[i])$. What I'm struggling with is how to add the element $B[i]$ once it has "passed this test" and how do I get the loop to move past $B[i]$ once it has failed the test. I'm not sure if I should be using for loops or while loops. Any help would be very much appreciated. Thank you.

Answer 1

You're right that you want to do some kind of loop. If I understand you correctly, you want to do this:

# assuming you have p, l, zeta, and B already defined
A = []
for b in B:
    keep_b = True
    for a in A:
        b_equiv_a = False
        for k in range(l):
            if a == zeta^k * b:
                b_equiv_a = True

        if b_equiv_a:
            keep_b = False

    if keep_b:
        A.append(b)

It's worth reading this carefully and trying to understand what it does. For each $b$, we check it against each $a$. If ever $b \sim a$, we set keep_b = False so that when we know to through $b$ out. If keep_b manages to be True at the end, that means it survived testing against each $a \in A$, so it's from a new equivalence class. We keep it, and now that it's in $A$ we'll check future $b$s against it as well.

There are slicker approaches (There's a couple obvious optimizations and I'm sure there's many that I don't see), but my goal with this code was ease-of-understanding. If you want to optimize it, you might ask on the sage forum or on stackoverflow.

---

I hope this helps ^_^