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

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

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

Background\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 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;
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])

μ  ^ function\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

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:

mu_R_G((3,6,12),5,3,VERBOSE) will calculate μ  ^(Z3×Z6×Z12,{5,3})\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')

Makers{\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 [ ]: