Shared2.2 / Math Research / RestrictedMuG.ipynbOpen in CoCalc
Author: Peter Francis
Views : 29

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

In [2]:
import numpy as np
import itertools as it
import math
from numba import njit


$\Large \text{Background}$

In [3]:
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
for i in range(len(N)):
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;

In [4]:
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)[:]}"

In [5]:
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))

In [7]:
@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])


$\Large \mu\hat{\;} \text{ function}$

In [8]:
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

In [9]:
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


$\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:

mu_R_G((3,6,12),5,3,VERBOSE) will calculate $\mu\hat{\;}(\mathbb{Z}_3\times\mathbb{Z}_6\times\mathbb{Z}_{12},\{5,3\})$

In [11]:
mu_R_G((6,),2,3,'e')

Finding μ^(G(6,),{2,3}). Checking 3≤|A|≤4. Checking: |A|=3 (20 cases) Found weak (2,3)-sum-free set, A=((1,), (2,), (3,)). Checking: |A|=4 (15 cases) There is no weak (2,3)-sum-free set of size 4.
'mu((6,), {2,3}) = 3 found A = [(1,), (2,), (3,)]'
In [ ]:
mu_R_G((2,2,2,),7,3,'e')


${\Large \text{Makers}}$

In [170]:
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

In [211]:
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

In [97]:
##  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)]
[]
In [252]:
### 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,8,9,10,11,12,13,14,15,16,17,
--------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) <ipython-input-252-b000aca88d7d> in <module>() 29 A = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6 30 ---> 31 if len(intersectW(RG_sumset([2], A, N),(RG_sumset([1], A, N)))) == 0: 32 print(f'Found weak (2,1)-sum-free set, A={A}.') 33 raise StopIteration <ipython-input-176-a6317c4c022c> in RG_sumset(H, A, N) 3 for h in H: 4 for i in it.combinations(A, h): # A is a tuple of tuples # i is a tuple of tuples ----> 5 SS = np.row_stack((SS, sum_of_elements_G(i,N))) # sum of elements is a numpy array 6 if len(A) < h: 7 return np.array([]) <ipython-input-79-0145364dcefc> in sum_of_elements_G(D, N) 8 modded = np.copy(addem) 9 for i in range(len(N)): ---> 10 modded[i] = addem[i] % N[i] 11 return modded # returns numpy array 12 KeyboardInterrupt: 
In [248]:
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)]
[]
In [174]:


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)]
In [93]:
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
In [108]:
mu(7,2,1)

2.0
In [ ]: