CoCalc Public Files2.2 / Math Research / RestrictedMu.ipynbOpen with one click!
Author: Peter Francis
Views : 63
Compute Environment: Ubuntu 18.04 (Deprecated)

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

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

Some Basics\Large \text{Some Basics}

In [2]:
def Zp(a,r): return it.product(range(a), repeat=r) def Z(a): return it.product(range(a), repeat=1) def Group(N): return list(it.product(*(range(n) for n in N))) def sum_of_elements(D, n): addem = np.array([0]*len(D[0])) for i in list(D): addem = (addem + np.array(list(i))) % n return addem def sum_of_elements_G(D, N): r = len(D) addem = np.array([0]*r) for i in list(D): addem = (addem + np.array(list(i))) modded = np.copy(addem) for i in range(len(N)): modded[i] = addem[i] % N[i] return modded def prod(N): prod = 1 for n in N: prod = prod * n return prod def intersectW(a,b): 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;

Use Functions\Large \text{Use Functions}

In [3]:
def SpecialReturn_old(u,r,k,l,A,n,verbose): if verbose == 's': return f"mu(Z_{n}^{r}, {{{k}, {l}}}) = {u} found A = {list(A)[:]}" if verbose == 't': return (n-m,A) if verbose == 'A': return A else: return u 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 [4]:
def sumsetR(H,A, n): SS = np.array([]) for m in H: for i in it.combinations(A,m): SS = np.union1d(np.array([np.remainder(np.sum(np.array(list(i))), n)]), SS) return np.unique(SS) def non_cyclic_sumsetR(H,A,n): SS = np.array([1,1]) for m in H: for i in it.combinations(A, m): # A is a tuple of tuples SS = np.row_stack((SS, sum_of_elements(i,n))) return np.unique(SS[1:], axis=0) def non_cyclic_Restricted_sumset(H,A,n): r = len(A[0]) SS = np.array([1]*r) for m in H: for i in it.combinations(A, m): # A is a tuple of tuples SS = np.row_stack((SS, sum_of_elements(i,n))) return np.unique(SS[1:], axis=0) def RG_sumset(H,A,N): SS = np.array([1]*len(A)) for h in H: for i in it.combinations(A, h): # A is a tuple of tuples SS = np.row_stack((SS, sum_of_elements_G(i,N))) 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)

μ functions\Large \mu \text{ functions}

In [5]:
def muR(n,r,k,l,verbose): for m in np.arange(n): for A in it.combinations(Z(n,1),n-m): if np.intersect1d(sumsetR([k],A,n), sumsetR([l],A,n)).size == 0: return SpecialReturn(n-m,r,k,l,A,n,verbose) def mu_Restricted_Square_Non_Cyclic(n,r,k,l,verbose): for m in range(n): for A in it.combinations(Z(n,2),n-m): # A is a tuple of tuples if intersectW(non_cyclic_sumsetR([k],A,n),(non_cyclic_sumsetR([l],A,n))).size == 0: return SpecialReturn(n-m,r,k,l,A,n,verbose) def mu_restricted_Znr(a,r,k,l,verbose): upperbound = ((a**r)-2+k+l)//(2) lowerbound = v(k-l,a,k+l)*(a**(r-1)) print('Finding mu(Z_',a,'^',r,',','{',k,',',l,'}). Checking: |A|=',lowerbound,'...', upperbound, ':') result = None for m in range(lowerbound,int(upperbound)): # is this correct for non cyclic groups? print(m) count = 0 for A in it.combinations(Zp(a,r),m): # A is a tuple of tuples count = count + 1 if (count % 100000) == 0: print("-----Count: ", count) if intersectW(non_cyclic_Restricted_sumset([k],A,a),(non_cyclic_Restricted_sumset([l],A,a))).size == 0: result = SpecialReturn_old(a**r-m - 1,r,k,l,A,a,verbose) break else: return result return result def mu_R_G(N,k,l): n = prod(N) verbose = 's' lowerbound = 1 upperbound = n G = Group(N) print(f'Finding μ(G{N},{{{k},{l}}}). Checking: |A|=',lowerbound,'...', upperbound, ':') result = None for m in range(lowerbound,upperbound+1,1): for A in it.combinations(G,m): # A is a tuple of tuples print(A) if intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N))).size == 0: result = m #SpecialReturn(m,k,l,A,N,verbose) break else: return result return result # why is this returning the first result it finds!?!?!

Playground\Large \text{Playground}

In [6]:
mu_restricted_Znr(3,2,2,1,'s')
Finding mu(Z_ 3 ^ 2 , { 2 , 1 }). Checking: |A|= 3 ... 5 : 3 4
'mu(Z_3^2, {2, 1}) = 4 found A = [(0, 1), (0, 2), (1, 0), (2, 0)]'
In [7]:
mu_R_G((3,3),2,1)
Finding μ(G(3, 3),{2,1}). Checking: |A|= 1 ... 9 : ((0, 0),)
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-7-31df0b08ba8d> in <module>() ----> 1 mu_R_G((3,3),2,1) <ipython-input-5-90aa8b974f0b> in mu_R_G(N, k, l) 44 for A in it.combinations(G,m): # A is a tuple of tuples 45 print(A) ---> 46 if intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N))).size == 0: 47 result = m #SpecialReturn(m,k,l,A,N,verbose) 48 break <ipython-input-4-703a0cbee07d> in RG_sumset(H, A, N) 26 for i in it.combinations(A, h): # A is a tuple of tuples 27 SS = np.row_stack((SS, sum_of_elements_G(i,N))) ---> 28 return np.unique(SS[1:], axis =0) 29 30 def D(n): /usr/local/lib/python3.6/dist-packages/numpy/lib/arraysetops.py in unique(ar, return_index, return_inverse, return_counts, axis) 243 # Must reshape to a contiguous 2D array for this to work... 244 orig_shape, orig_dtype = ar.shape, ar.dtype --> 245 ar = ar.reshape(orig_shape[0], -1) 246 ar = np.ascontiguousarray(ar) 247 dtype = [('f{i}'.format(i=i), ar.dtype) for i in range(ar.shape[1])] ValueError: cannot reshape array of size 0 into shape (0,newaxis)
In [ ]:
def mu_R_G2(N,k,l): n = prod(N) verbose = 's' lowerbound = 1 upperbound = n G = Group(N) print(f'Finding μ(G{N},{{{k},{l}}}). Checking: |A|=',lowerbound,'...', upperbound, ':') result = None for m in range(lowerbound,upperbound): print("m=",m) print("combos=", list(it.combinations(G,m))) for A in it.combinations(G,m): # A is a tuple of tuples print("A=",A) print("2^A=",RG_sumset([k],A,N),'... 1^A=',(RG_sumset([l],A,N))) if intersectW(RG_sumset([k],A,N),(RG_sumset([l],A,N))).size == 0: result = m return result
In [ ]:
mu_R_G2((3,3),2,1)
In [ ]:
Group((2,3))
In [ ]: