Shared2.2 / Math Research / RestrictedMuG.ipynbOpen in CoCalc

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

import numpy as np
import itertools as it
import math
from numba import njit

Background\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 list
    intersection = []
    for arow in range(len(a)):
        for brow in range(len(b)):
            if (a[arow] == b[brow]).all():
                intersection = intersection + [tuple(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)

@njit
def D(n):
    output = np.array([n])
    for i in range(1,n):
        if (n % i) == 0:
            output = np.concatenate((output,np.array([i])))
    return output

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)

def mu(n,k,l):
    stuff = []
    for d in D(n):
        delta = math.gcd(d,k-l)
        r = l*math.ceil((d-delta)/(k+l)) % delta
        stuff = stuff + [math.ceil((d-(delta-r))/(k+l))*(n/d)]
    return int(max(stuff))
@njit
def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

@njit`
def PrimeD(n):
    return np.array([i for i in D(n) if isPrime(i) and i!=1])

μ  ^ function\Large \mu\hat{\;} \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
    count = 0
    otherway = False

    if type(N) is int:
        N = (N,)
    test = False
    for n in range(len(N)-1):
        if (N[n+1] % N[n]) != 0:
            test = True
            count = count + 1
    if test == True:
        if count == len(N)-1:
            otherway = True
            exponent = 1
        elif count != len(N)-1:
            return 'ERROR: Tuple of cyclic orders must be listed invariently.'
    elif test == False:
        exponent = N[-1]

    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,exponent,k+l)*(n/exponent))
    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')
        if otherway == True:
            print(f'The group entered, G{N} is isomorphic to G({n}).\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 len(intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N)))) == 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
def mu_R_G_Manual(N,k,l,low,high,verbose):  # takes a tuple of integers as the group (product of cyclic groups with orders....), and two integers, k and l

    if type(N) is int:
        N = (N,)

    n = prod(N)     # finds the product of the orders, the size of the group
    
    if high > n:
        return 'error -- out of bounds.'
    
    G = Group(N)    # G is a list of tuples
    if verbose == 'e':
        print(f'Finding μ^(G{N},{{{k},{l}}}). Checking {low}≤|A|≤{high}.\n')
    result = None
    for m in range(low,high+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 len(intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N)))) == 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

Playground\Large \text{Playground}

The imputs are NN, kk, ll, and verbose. NN can either be a tuple of integers or an integer and kk and ll 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:

will calculate μ  ^(Z3×Z6×Z12,{5,3})\mu\hat{\;}(\mathbb{Z}_3\times\mathbb{Z}_6\times\mathbb{Z}_{12},\{5,3\})

Makers{\Large \text{Makers}}

def AMaker3x3(w):
    A0 = list(((0,(2*a+1)%(3*w)) for a in range(((-w-1)//2),((w+1)//2)%(3*w))))
    A1 = list(((1,2*b) for b in range(int(w))))
    A2 = list(((2,(-2*c)%(3*w)) for c in range(int(w))))
    return A0+A1+A2
def AMaker7x7(w):
    A0 = [i for i in np.arange(+1,2)]
    A1 = [i for i in np.arange(+1,2)]
    A2 = [i for i in np.arange(+1,2)]
    A3 = [i for i in np.arange(+1,2)]
    A4 = [i for i in np.arange(+1,2)]
    A5 = [i for i in np.arange(+1,2)]
    A6 = [i for i in np.arange(+1,2)]
    return A0+A1+A2+A3+A4+A5+A6
##  Z_7 x Z_7

A_0 = list(it.product([0],[6,1,3]))
A_1 = list(it.product([1],[0,2]))
A_2 = list(it.product([2],[1,3]))
A_3 = list(it.product([3],[2,4]))
A_4 = list(it.product([4],[3,5]))
A_5 = list(it.product([5],[4,6]))
A_6 = list(it.product([6],[5,0]))


A = A_0+A_1+A_2+A_3+A_4+A_5+A_6

print(A)

# print(RG_sumset([2],A,(7,int(7*w))))
# print(RG_sumset([2],A,(7,int(7*w))))

intersectW(RG_sumset([2],A,(7,7)),RG_sumset([1],A,(7,7)))
[(0, 6), (0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4), (5, 6), (6, 5), (6, 0)]
[]
### Brute forcing with some initial conditions


n = 7 * 21
N = (7, 21)

m = 50


A_0 = list(it.product([0],[14,16,18,20,1,3,5,7]))


for a in range(21):
    print(f'\n a={a}')
    print(f'       b=', end='')
    A_1 = list(it.product([1], [(a + i) % 21 for i in range(0, 14, 2)]))
    for b in range(21):
        print(f'{b},', end='')
        A_2 = list(it.product([2], [(b + i) % 21 for i in range(0, 14, 2)]))
        for c in range(21):
            A_3 = list(it.product([3], [(c + i) % 21 for i in range(0, 14, 2)]))
            for d in range(21):
                A_4 = list(it.product([4], [(d + i) % 21 for i in range(0, 14, 2)]))
                for e in range(21):
                    A_5 = list(it.product([5], [(e + i) % 21 for i in range(0, 14, 2)]))
                    for f in range(21):
                        A_6 = list(it.product([6], [(f + i) % 21 for i in range(0, 14, 2)]))

                        A = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6

                        if len(intersectW(RG_sumset([2], A, N),(RG_sumset([1], A, N)))) == 0:
                            print(f'Found weak (2,1)-sum-free set, A={A}.')
                            raise StopIteration
a=0 b=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20, a=1 b=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20, a=2 b=0,1,2,3,4,5,6,7,
A_0 = list(it.product([0],[14,16,18,20,1,3,5,7]))
A_1 = list(it.product([1],[0,2,4,6,8,10,12]))
A_2 = list(it.product([2],[]))
A_3 = list(it.product([3],[]))
A_4 = list(it.product([4],[]))
A_5 = list(it.product([5],[]))
A_6 = list(it.product([6],[9,11,13,15,17,19,0]))

A = A_0+A_1+A_2+A_3+A_4+A_5+A_6

print(A)

print('A_0=',A_0)
print('A_1=',A_1)
print('A_2=',A_2)
print('A_3=',A_3)
print('A_4=',A_4)
print('A_5=',A_5)
print('A_6=',A_6)

# print(RG_sumset([2],A,(7,int(7*w))))
# print(RG_sumset([2],A,(7,int(7*w))))

intersectW(RG_sumset([2],A,(7,21)),RG_sumset([1],A,(7,21)))
[(0, 14), (0, 16), (0, 18), (0, 20), (0, 1), (0, 3), (0, 5), (0, 7), (1, 0), (1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (1, 12), (6, 9), (6, 11), (6, 13), (6, 15), (6, 17), (6, 19), (6, 0)] A_0= [(0, 14), (0, 16), (0, 18), (0, 20), (0, 1), (0, 3), (0, 5), (0, 7)] A_1= [(1, 0), (1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (1, 12)] A_2= [] A_3= [] A_4= [] A_5= [] A_6= [(6, 9), (6, 11), (6, 13), (6, 15), (6, 17), (6, 19), (6, 0)]
[]


A_0 = list(it.product([0],[i % 49 for i in np.arange(42-49,27+1,2)]))
A_1 = list(it.product([1],[i % 49 for i in np.arange(0,30+1,2)]))
A_2 = list(it.product([2],[i % 49 for i in np.arange(7,37+1,2)]))
A_3 = list(it.product([3],[i % 49 for i in np.arange(14,44+1,2)]))
A_4 = list(it.product([4],[i % 49 for i in np.arange(21-49,2+1,2)]))
A_5 = list(it.product([5],[i % 49 for i in np.arange(28-49,9+1,2)]))
A_6 = list(it.product([6],[i % 49 for i in np.arange(35-49,16+1,2)]))

# A = A_0+A_1+A_2+A_3+A_4+A_5+A_6

print('A_0=',A_0)
print('A_1=',A_1)
print('A_2=',A_2)
print('A_3=',A_3)
print('A_4=',A_4)
print('A_5=',A_5)
print('A_6=',A_6)

# print(RG_sumset([2],A,(7,int(7*w))))
# print(RG_sumset([2],A,(7,int(7*w))))

intersectW(RG_sumset([2],A,(7,49)),RG_sumset([1],A,(7,49)))
A_0= [(0, 42), (0, 44), (0, 46), (0, 48), (0, 1), (0, 3), (0, 5), (0, 7), (0, 9), (0, 11), (0, 13), (0, 15), (0, 17), (0, 19), (0, 21), (0, 23), (0, 25), (0, 27)] A_1= [(1, 0), (1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (1, 12), (1, 14), (1, 16), (1, 18), (1, 20), (1, 22), (1, 24), (1, 26), (1, 28), (1, 30)] A_2= [(2, 7), (2, 9), (2, 11), (2, 13), (2, 15), (2, 17), (2, 19), (2, 21), (2, 23), (2, 25), (2, 27), (2, 29), (2, 31), (2, 33), (2, 35), (2, 37)] A_3= [(3, 14), (3, 16), (3, 18), (3, 20), (3, 22), (3, 24), (3, 26), (3, 28), (3, 30), (3, 32), (3, 34), (3, 36), (3, 38), (3, 40), (3, 42), (3, 44)] A_4= [(4, 21), (4, 23), (4, 25), (4, 27), (4, 29), (4, 31), (4, 33), (4, 35), (4, 37), (4, 39), (4, 41), (4, 43), (4, 45), (4, 47), (4, 0), (4, 2)] A_5= [(5, 28), (5, 30), (5, 32), (5, 34), (5, 36), (5, 38), (5, 40), (5, 42), (5, 44), (5, 46), (5, 48), (5, 1), (5, 3), (5, 5), (5, 7), (5, 9)] A_6= [(6, 35), (6, 37), (6, 39), (6, 41), (6, 43), (6, 45), (6, 47), (6, 0), (6, 2), (6, 4), (6, 6), (6, 8), (6, 10), (6, 12), (6, 14), (6, 16)]
[(0, 5), (0, 7), (0, 9), (0, 11), (0, 13), (0, 15), (0, 17), (1, 6), (1, 8), (1, 10), (1, 12), (1, 14), (1, 16), (1, 18), (1, 20), (1, 22), (1, 24), (1, 26), (1, 28), (1, 30), (2, 1), (2, 3), (2, 5), (2, 7), (2, 9), (2, 11), (2, 13), (2, 15), (2, 17), (2, 19), (2, 21), (2, 23), (2, 25), (2, 27), (2, 29), (2, 31), (3, 2), (3, 4), (3, 6), (3, 8), (3, 10), (3, 12), (3, 14), (3, 16), (3, 18), (3, 20), (3, 22), (3, 24), (3, 26), (3, 28), (3, 30), (3, 32), (4, 3), (4, 5), (4, 7), (4, 9), (4, 11), (4, 13), (4, 15), (4, 17), (4, 19), (4, 21), (4, 23), (4, 25), (4, 27), (4, 29), (4, 31), (4, 33), (5, 4), (5, 6), (5, 8), (5, 10), (5, 12), (5, 14), (5, 16), (5, 18), (5, 20), (5, 22), (5, 24), (5, 26), (5, 28), (5, 30), (5, 32), (5, 34), (6, 5), (6, 7), (6, 9), (6, 11), (6, 13), (6, 15)]
print('w ---- G ----- |A|')
for w in range(1,10,2):
    if 2 not in PrimeD(w)%3:
        if len(intersectW(RG_sumset([2],AMaker3(w),(3,int(3*w))),RG_sumset([1],AMaker3(w),(3,int(3*w))))) == 0:
            print(f'{w}----3x{3*w}---{len(AMaker(w))}')
        else:
            print('Found Counterexample!')
            break
w ---- G ----- |A| 1----3x3---4 3----3x9---10 7----3x21---22 9----3x27---28
mu(7,2,1)
2.0