Distributive on myself

Question

Background

We all know about distributivity, i.e. \$a(b+c) = ab + ac\$. This is a property on 2 different operations, namely addition and multiplication. But indeed, nothing can stop us from studying distributivity of 1 operation. In this challenge, you will be studying a kind of left-distributive operation.

Task

Given a positive integer \$N\$. Consider an operation \$p \star q\$ where \$p, q\in\{0, 1,\dots, N-1\}\$, such that \$ p \star 1 \equiv p + 1 \pmod N\$ and \$p \star (q \star r) = (p \star q) \star (p \star r)\$. In essence, you are making an \$N\times N\$ table. For instance, if \$N = 4\$, a possible \$\star\$ is:

⋆ q 0 1 2 3
p-+---------
0 | 0 1 2 3
1 | 0 2 0 2 ←
2 | 0 3 0 3
3 | 0 0 0 0
      ↑

Note that the marked column satisfies \$ p \star 1 \equiv p + 1 \pmod N\$. In this challenge, we are interested in the marked row. It seems to be periodic, and the challenge is to find its period. The smallest positive period for a sequence \$a_0, \dots , a_{N-1}\$, is defined to be the smallest positive integer \$k\$, such that \$k\$ divides \$N\$, and \$a_i = a_{i + k}\$, for \$i=0..(N-k-1)\$.

However, there may be many possible \$\star\$'s for a given \$N\$, or there may be none. So you need to compute the (smallest positive) periods for all of them.

Task: given a positive integer N, compute all the possible smallest positive periods of 1 ⋆ q. This is code-golf.

Details and clarifications

In the case N = 4, the given table turns out to be the only possible one, so you should output a list (or a set, etc.) consisting only of the number 2. But for N = 3, no operation satisfies all the requirements, so you can output an empty list, or 0, or some falsy value.

The smallest positive period will always be between 1 and \$N\$, if the sequence 1 ⋆ q (0 <= q < N) doesn't repeat at all, it is of period \$N\$.

N will range from 1 to \$2^{32}-1\$. So it is almost kolmogorov-complexity. But note that a formula or recurrence relation of this is unknown.

Test cases

In : N = 1
Out: [1]

In : N = 2
Out: [1]

In : N = 3
Out: []

In : N = 4
Out: [2]

Answer 1

Python 2, 113 bytes

N=input()
f=lambda p,q:f(f(p,q-1),-~p%N)if p*q else q
print([i for i in range(1,N)if N%i+f(1,i)<1]+[N])[:N&N-1<1]

-2 bytes thanks to @Jakque

Try it online!

The short, recursive approach is slow since it repeats computation of many entries, so I've made an iterative, memoized approach which is much faster (quadratic in N) and can compute up to N=4096 within 60 seconds on TIO.

How it Works

The algorithm assumes that \$\star\$ is unique, if it exists (proof below). It uses recursion, setting

\$p\star q=\begin{cases} q, &p=0 \\ p+1 \mod n, &q=1 \\ (p \star (q-1 \mod n))\star (p+1 \mod n), &\text{otherwise} \end{cases}\$

The first case (\$p=0\$) is Lemma 1 in the uniqueness proof: \$0\star q=q\$.

The second case (\$q=1\$) is given.

The third case has a simple proof despite its complex self (assuming addition and subtraction are mod \$N\$:

\begin{align*} &p \star q\\ =&p \star ((q-1)+1) \\ =&p \star ((q-1)\star 1) \\ =&(p \star (q-1))\star(p\star 1) \\ =&(p \star (q-1))\star(p+1) \end{align*}

This is enough to determine the unique \$\star\$ (The proof shows that the third case will not recurse indefinitely).

The period is the minimum \$i\$ such that \$1\star (i+1) = 1\star 1 = 2\$. If this \$i\$ doesn't divide \$N\$, then it is not a period.

Ungolfed code:

# f(p,q,N) = p⋆q
def f(p,q,N):
    if p==0:
        return q
    if q==1:
        return (p+1)%N
    return f(f(p,(q-1)%N,N),(p+1)%N, N)

def period(N):
    if any(f(p,f(q,r,N),N) != f(f(p,q,N),f(p,r,N),N) for p in range(N) for q in range(N) for r in range(N)):
        # The f does not exist
        return []
    for i in range(1, N):
        # period is i if f(1,i+1)=f(1,1)=2
        if f(1,i+1,N) == 2:
            # might not be divisible, in which case it is not the period
            if N%i:
                return [N]
            return [i]

This could be sped up immensely by memoization utilizing \$ a \star 2 = a \star (1 \star 1) = (a\star 1)\star (a\star 1) = (a+1)\star(a+1) \$ and \$1 \star a = (1\star (a-1))\star 2\$.

Proof of Uniqueness of \$\star\$

For this section, we assume all addition/subtraction is mod \$N\$.

Lemma 1: For all \$a\$, \$0 \star a = a\$

Proof: Induction

Base case: \$a=1\$. Given since \$0\star 1=1\$.

Step: Assume this lemma holds for \$a=k\$. Then \begin{align*} &0 \star (k + 1)\\ =& 0\star (k\star 1) \\ =& (0\star k)\star (0\star 1) \\ =& k \star 1 \\ =& k+1, \end{align*} so this holds for \$a=k+1\$. Since this addition is mod \$N\$, this will "wrap around" back to \$0\$, so it applies for \$a=0\$ too, not just \$a\geq 1\$

Theorem: If an operation \$\star\$ is valid for a given \$N\$, then it the unique \$\star\$ that is valid for that \$N\$.

Proof: We use strong induction to show that, for all \$0\leq a,b\leq N-1\$, \$a\star b\$ is uniquely determined by \$N\$. In addition, for each \$a\$ and \$b\$ in the same set, either (1) \$a\star b=0\$ or (2) \$a<a\star b<N\$

1. Base case: \$a\star b\$ is uniquely determined and equal to \$0\$ for \$a=N-1\$ and for all \$b\$.

   We prove this base case with induction too.

   1. Base case: \$b=1\$. We are given \$a\star 1=a+1\$, so \$(N-1)\star 1=0\$, uniquely determined.
   2. Step: Given \$(N-1)\star b=0\$ for \$b=k\$, then \begin{align*} &(N-1)\star (b+1)\\ =&(N-1)\star (b\star 1)\\ =&((N-1)\star b)\star((N-1)\star 1)\\ =&0\star0 \\ =&0, \end{align*} where we use Lemma 1 to show \$0\star 0=0\$, so \$(N-1)\star b\$ is uniquely determiend to be \$0\$.

2. Assume \$a\star b\$ is uniquely determined and either (1) or (2) hold for all \$k<a\leq N-1\$ and for all \$b\$. Then for \$a=k\$, we will show \$a\star b\$ is uniquely determined and either (1) or (2) hold for all \$b\$, again with induction.

   1. Base case: \$k\star b\$ is uniquely determined and either (1) or (2) hold for \$b=1\$. This is trivial since \$k\star 1=k+1>k\$, so \$k\star 1\$ is unique and (2) holds

   2. Step: Assume \$k\star b\$ is uniquely determined and either (1) or (2) hold for \$b=j\$. Then: \begin{align*} &k\star (b+1)\\ =&k\star (b\star 1)\\ =&(k\star b)\star(k\star 1)\\ =&(k\star b)\star(k+1) \end{align*} If (1) holds, then \$k\star b=0\$, so \$k\star(b+1)=k+1>k\$ by Lemma 1. Thus \$k\star(b+1)\$ is uniquely determined and satisfies (2).

      If (2) holds, then \$k<k\star b\leq N-1\$,so by the outer inductive assumption, \$k\star(b+1)=(k\star b)\star (k+1)\$ is uniquely determined and either (1) or (2) holds for it.

      In either case, \$k\star(b+1)\$ is uniquely determined and either (1) or (2) hold for it, completing the inductive step.

Answer 2

Wolfram Language (Mathematica), 106 90 42 bytes

AtomQ@#&&2^Tr@UnitStep[#-{2,3,5,9}]&@*Log2

Try it online!

Returns the period if it exists, or False otherwise.

Laver Tables exist iff \$N\$ is a power of 2. The sequence of periods is A098820 on the OEIS.

Assuming the l3 rank-into-rank cardinal exists, it's been shown that the first \$N\$ for which the period is greater than 16 is at least \$2^{A(9,A(8,A(8,255)))}\ggg2^{31}-1\$, where \$A\$ is the Ackermann function. John Baez has a relatively accessible layman's explanation here.