RestrictedMuG.ipynb

Kernel: Python 3 (Ubuntu Linux)

$${\Huge\mu\hat{\;}(G,\{k,l\})}$$

import numpy as np
import itertools as it
import math

$\Large \text{Background}$

def Group(N):  # takes a tuple of integers and outputs a list of tuples
    return list(it.product(*(range(n) for n in N)))

def sum_of_elements_G(D, N):         # D is a tuple of tuples that have to be the same size       # N is a tuple of integers
    addem = np.array([0]*len(N))     # numpy array that is the the length of the tuples in D
    for i in list(D):                # i is a tuple
        addem = (addem + np.array(list(i)))
    modded = np.copy(addem)
    for i in range(len(N)):
        modded[i] = addem[i] % N[i]
    return modded      # returns numpy array

def choose(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

def prod(N):
    prod = 1
    for n in N:
        prod = prod * n
    return prod

def intersectW(a,b):  # takes two 2D numpy arrays and outputs one 2D numpy array
    intersection = np.array([])
    for arow in range(len(a)):
        for brow in range(len(b)):
            if (a[arow] == b[brow]).all():
                intersection = np.union1d(intersection, a[arow])
    return intersection;

def SpecialReturn(u,k,l,A,N,verbose):
    if verbose == 'u':
        return u
    if verbose == 't':
        return (u,A)
    if verbose == 'A':
        return A
    else:
        return f"mu({N}, {{{k},{l}}}) = {u}       found A = {list(A)[:]}"

def RG_sumset(H,A,N):
    SS = np.array([[1]*len(N)])
    for h in H:
        for i in it.combinations(A, h):       # A is a tuple of tuples         # i is a tuple of tuples
            SS = np.row_stack((SS, sum_of_elements_G(i,N))) # sum of elements is a numpy array
    if len(A) < h:
        return np.array([])
    else:
        return np.unique(SS[1:], axis=0)

def D(n):
    list = np.array([n])
    for i in range(1,n):
        if (n % i) == 0:
            list = np.append(list,[i])
    return list

def v(g,n,h):
    ans = 0
    for d in D(n):
        p = (((d-1-math.gcd(d,g))//h)+1)*(n/d)
        if p > ans:
            ans = p
    return int(ans)

$\Large \mu \text{ function}$

def mu_R_G(N,k,l,verbose):  # takes a tuple of integers as the group (product of cyclic groups with orders....), and two integers, k and l
    match = False
    if type(N) is int:
        N = (N,)
    for n in range(len(N)-1):
        if (N[n+1] % N[n]) != 0:
            return 'ERROR: Tuple of cyclic orders must be listed invariently.'
    n = prod(N)     # finds the product of the orders, the size of the group
    upperbound = (n-2+k+l)//(2)
    lowerbound = int(v(k-l,N[-1],k+l)*(n/N[-1]))+1
    if upperbound == lowerbound:
        if verbose == 'e':
            print(f'Upper and lower bounds match so μ(G{N},{{{k},{l}}}) = {upperbound}\n')
            match = True
        if verbose == 'u':
            return upperbound
    G = Group(N)    # G is a list of tuples
    if verbose == 'e' and match == False:
        print(f'Finding μ(G{N},{{{k},{l}}}). Checking {lowerbound}≤|A|≤{upperbound}.\n')
    result = None
    for m in range(lowerbound,upperbound+1,1):
        if verbose == 'e':
            print(f'Checking: |A|={m}   ({choose(n,m):,} cases)')
        for A in it.combinations(G,m):       # A is a tuple of tuples
            if intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N))).size == 0:
                if verbose == 'e':
                    result = SpecialReturn(m,k,l,A,N,'s')
                    print(f'      Found weak ({k},{l})-sum-free set, A={A}.')
                else:
                    result = SpecialReturn(m,k,l,A,N,verbose)
                break
        else:
            if verbose == 'e':
                print(f'      There is no weak ({k},{l})-sum-free set of size {m}.')
            return result
    return result

$\Large \text{Playground}$

The imputs are $N$, $k$, $l$, and verbose. $N$ can either be a tuple of integers or an integer and $k$ and $l$ must be integers.

verbose =

• 'u' outputs just the integer value of mu

• 's' outputs a string with mu and a found A

• 't' outputs a tuple with mu and a found A

• 'A' outputs a found A

• 'e' outputs the same as 's' along with progess

Example:

ParseError: KaTeX parse error: Expected 'EOF', got '_' at position 11: \texttt{mu_̲R_G((3,6,12),5,… will calculate $\mu\hat{\;}(\mathbb{Z}_3\times\mathbb{Z}_6\times\mathbb{Z}_{12},\{5,3\})$

mu_R_G((5,5),2,1,'e')

Finding μ(G(5, 5),{2,1}). Checking 11≤|A|≤13.

Checking: |A|=11   (4,457,400 cases)

def mu_R_G2(N,k,l,verbose):  # takes a tuple of integers as the group (product of cyclic groups with orders....), and two integers, k and l
    match = False
    if type(N) is int:
        N = (N,)
    for n in range(len(N)-1):
        if (N[n+1] % N[n]) != 0:
            return 'ERROR: Tuple of cyclic orders must be listed invariently.'
    n = prod(N)     # finds the product of the orders, the size of the group
    upperbound = (n-2+k+l)//(2)
    lowerbound = int(v(k-l,N[-1],k+l)*(n/N[-1]))+1
    if upperbound == lowerbound:
        if verbose == 'e':
            print(f'Upper and lower bounds match so μ(G{N},{{{k},{l}}}) = {upperbound}\n')
            match = True
        if verbose == 'u':
            return upperbound
    G = Group(N)    # G is a list of tuples
    if verbose == 'e' and match == False:
        print(f'Finding μ(G{N},{{{k},{l}}}). Checking {lowerbound}≤|A|≤{upperbound}.\n')
    result = None
    for m in range(lowerbound,upperbound+1,1):
        if verbose == 'e':
            print(f'Checking: |A|={m}   ({choose(n,m):,} cases)')
        for A in it.combinations(G,m):       # A is a tuple of tuples
            if intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N))).size == 0:
                if verbose == 'e':
                    result = SpecialReturn(m,k,l,A,N,'s')
                    print(f'      Found weak ({k},{l})-sum-free set, A={A}.')
                else:
                    result = SpecialReturn(m,k,l,A,N,verbose)
                break
        else:
            if verbose == 'e':
                print(f'      There is no weak ({k},{l})-sum-free set of size {m}.')
            return result
    return result

$\Large \text{Data}$

Finding μ(G(3, 3),{2,1}). Checking 3≤|A|≤5.

Checking: |A|=3   (84 cases)
      Found weak (2,1)-sum-free set, A=((0, 1), (0, 2), (1, 0)).
Checking: |A|=4   (126 cases)
      Found weak (2,1)-sum-free set, A=((0, 1), (0, 2), (1, 0), (2, 0)).
Checking: |A|=5   (126 cases)
      There is no weak (2,1)-sum-free set of size 5.

mu((3, 3), {2,1}) = 4       found A = [(0, 1), (0, 2), (1, 0), (2, 0)]

Finding μ(G(3, 9),{2,1}). Checking 9≤|A|≤14.

Checking: |A|=9   (4,686,825 cases)
      Found (2,1) weak (2,1)-sum-free set, A=((0, 1), (0, 3), (0, 6), (0, 8), (1, 0), (1, 2), (1, 4), (2, 0), (2, 5)).
Checking: |A|=10   (8,436,285 cases)
      Found (2,1) weak (2,1)-sum-free set, A=((0, 1), (0, 3), (0, 6), (0, 8), (1, 0), (1, 2), (1, 4), (2, 0), (2, 5), (2, 7)).
Checking: |A|=11   (13,037,895 cases)
      There is no weak (2,1)-sum-free set of size 11.

mu((3, 9), {2,1}) = 10       found A = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 0), (1, 2), (1, 4), (2, 0), (2, 5), (2, 7)]