./0000700000175000017500000000000014527045327013212 5ustar cloudconvertcloudconvert./isHeffter.m0000644000175000017500000000061214525623672015323 0ustar cloudconvertcloudconvertfunction H = isHeffter(A,B) % Constructs the array having the Heffter systems A and B % as rows and columns n = size(A,1); H = zeros(n); G = sort(A(:)); for i = 1:length(G) posA = find(A==G(i)); posB = find(B==G(i)); rigA = mod(posA,n); rigB = mod(posB,n); if rigA==0 rigA=n; endif if rigB ==0 rigB=n; endif H(rigA,rigB) = G(i); endfor ./readme.txt0000644000175000017500000000400614525626140015216 0ustar cloudconvertcloudconvertImplemented for Gnu Octave / Matlab Main file: main_Heffter_Systems At the beginning of the code of the main it is possible to choose: - the dimension n of the array, that can be either 3 or 4; - the dimension t of the subgroup of Z_2nk+t The number of filled cells in each row and column k is set to be 3, and should not be changed. The code finds all the orthogonal Heffter systems on the set of symbols [1,2nk+t]\J, where J is the subgroup of Z_2nk+t of order t. In particular, it computes for each pair of orthogonal systems one possible representation of the resulting weak Heffter array, that is stored in absolute value in the structure H. At the moment, the code does not perfectly distinguish whenever the resulting array is classical or strictly weak. In any case, given the absolute value of the weak Heffter array, that is H{i} (line 38, main_Heffter_Systems.m ), it tries to assign the signs in order to construct the classical Heffter array. If it succeeds, the classical Heffter array is stored in the structure classical_heffter (line 41, main_Heffter_Systems.m), otherwise it is stored in possibly_strict_heffter (line 43, main_Heffter_Systems.m). The output of the code is given by the two structures classical_heffter and possibly_strict_heffter, that to summarize are: - classical_heffter : a subset of the classical Heffter arrays on the symbol set [1,2nk+t]\J; - possibly_strict_heffter: a subset of the weak Heffter arrays on the symbol set [1,2nk+t]\J. The union of these two structures gives all the possible weak Heffter arrays on the symbol set [1,2nk+t]\J, where various techniques were employed to avoid as many repetition as possible of the same array. To verify whether there exists a strictly weak Heffter array, at the moment it is necessary to verify by hand if it is possible to assign the signs of the arrays of possibly_strict_heffter. For the set of parameters of interest there are not that many arrays in possibly_strict_heffter, so this step could be easily performed. ./zero_sum_triples.m0000644000175000017500000000075714524635540017017 0ustar cloudconvertcloudconvertfunction Triples= zero_sum_triples(A,v) % find the zero sum triples in the set A, modulo v A1 = A; A2 = [-A]; A3 = A-v; Triples= []; for i = 1:length(A) el1 = A(i); for j = i+1:length(A) el2 = A(j); t = -(el1 + el2); if ~isempty(find(A2 == t)) pos = find(A2 == t); Triples = [Triples; [el1 el2 A1(pos)] ]; elseif ~isempty(find(A3==t)) pos = find(A3 == t); Triples = [Triples; [el1 el2 A1(pos)] ]; endif endfor endfor ./Heffter_systems_n_3.m0000644000175000017500000000713314525730624017316 0ustar cloudconvertcloudconvertfunction H = Heffter_systems_n_3(n,k,t) v = 2*n*k+t; % Dimension of the group Sym = 1:v/2; % Symbols of an half set % Minus the subgroup of size t aux = find(mod(Sym,v/t)==0); Sym(aux) = []; Triples = zero_sum_triples(Sym,v); % Zero-sum triples in Sym % Without loss of generality, we assume that the first row and the first % column contain the element 1 (or -1) aux1 = Triples(:,1); pos = find(aux1==1); A1 = Triples(pos,:); pos = find(aux1~=1); A2 = Triples(pos,:); A3 = A2; % When two zero sum triples of A2 are compatibles? A_int = zeros(size(A2)); for i = 1:size(A2,1) for j = i+1:size(A2,1) if length(intersect(A2(i,:), A2(j,:)))==0 A_int(i,j) = 1; endif endfor endfor A_int = A_int+A_int'; found = 0; noniso = 0; database = []; for i1 = 1:size(A1,1) b1 = A1(i1,:); % First subset of Heffter system for i2 = 1:size(A2,1) b2 = A2(i2,:); % Second subset of Heffter system G = [b1, b2]; index2 = find(A_int(i2,:)); % search the third subset between % the compatible ones if length(unique(G)) ==length(G) for i3 = 1:size(A3(index2,:),1) b3 = A3(index2(i3),:); % Third subset of Heffter system G = [b1, b2,b3]; index3 = intersect(index2,find(A_int(index2(i3),:))); if length(unique(G)) ==length(G) % G is an Heffter system G = [b1; b2;b3]; found = found+1; new_Heffter_System = true; if noniso>0 % Is this a new Heffter system, or is it an old one? for ijk = 1:length(database) Old_Heffter = database{ijk}; % Check if every row contains the same elements: for row_index = 1:size(G,1) if max(abs(sort(G(row_index,:)) - sort(Old_Heffter(row_index,:))))==0 new_Heffter_System = false; endif endfor endfor if (new_Heffter_System == true) noniso = noniso+1; database{noniso} = G; endif else noniso = noniso+1; database{noniso} = G; endif endif endfor endif endfor endfor disp('Heffter systems for these parameters:') database % These are all the Heffter systems on the set of % symbols Sym % Can we find two Heffter Systems inside of database that are % orthogonal? mm = length(database); num_orthogonal = 0; H = []; for i = 1:mm A1 = database{i}; % Fix one Heffter system for j = i+1:mm A2 = database{j}; % And the second one orthogonal = true; for k1 = 1:size(A1,1) % And now check if they are orthogonal for k2 = 1:size(A2,1) if length(intersect(A1(k1,:),A2(k2,:)))>1 orthogonal = false; endif endfor endfor if orthogonal % If they are orthogonal, construct the array Heff_array = isHeffter(A1,A2); % Before adding the array to the database, check if it is already there isnew = true; Heff_array1 = Heff_array(:,1); [~,idx1] = sort(Heff_array1); Heff_array = Heff_array(idx1,:); for kk = 1:length(H) C = H{kk}; C1= C(:,1); % As before, check up to a permutation of the rows if max(abs(sort(Heff_array1) - sort(C1))) == 0 [~,idx2] = sort(C1); C = C(idx2,:); endif if norm(C - Heff_array)==0 isnew = false; endif endfor if isnew num_orthogonal = num_orthogonal + 1; H{num_orthogonal} = Heff_array; endif endif endfor endfor ./test_strictly_weak1.m0000644000175000017500000000362114525626720017410 0ustar cloudconvertcloudconvertfunction [B,G] = test_strictly_weak1(A,v) % tries to construct a classical Heffter array starting from A; % the output is the result of this guess: if the array B is an % all-one matrix, then the array G is a classical Heffter array. % we give an assigned value (+1 or -1) to each entry of the array A when % reading the elements along the rows, or along the columns, in order to have % zero sum. assigned = zeros(size(A,1),size(A,2)); n = size(A,1); m = size(A,2); for i = 1:n [val,pos] = max(A(i,:)); % Finds the element whose sign has to change non_empty_positions = find(A(i,:)); assigned_row(i,non_empty_positions) = 1; if mod(sum(A(i,:)),v)~= 0 assigned_row(i,pos) = -1; % and change it (after checking that it is necessary % to have a+b = c ) endif endfor A = A'; for i = 1:m [val,pos] = max(A(i,:)); non_empty_positions = find(A(i,:)); assigned_col(i,non_empty_positions) = 1; if mod(sum(A(i,:)),v)~= 0 assigned_col(i,pos) = -1; endif endfor assigned_col = assigned_col'; A = A'; % ... and do the same for the columns for i =1:m for j = 1:n if assigned_row(i,j) ~=assigned_col(i,j) % if two elements have different signs, % change the signs in the whole column assigned_col(:,j) = -assigned_col(:,j); endif endfor endfor B = (A.*assigned_row)==(A.*assigned_col); aux1 = sum(B.*(A~=0),2); aux2 = sum(B,1); g1 = find(aux1==0); g2 = find(aux2==0); for j = 1:length(g1) assigned_row(g1(j),:) = -assigned_row(g1(j),:); endfor B = (A.*assigned_row)==(A.*assigned_col); aux2 = sum(B.*(A~=0),2); g2 = find(aux2==0); for j = 1:length(g2) assigned_row(:,g2(j)) = -assigned_row(:,g2(j)); endfor % if the two arrays are still different, then the array is not a classical Heffter B = (A.*assigned_row)==(A.*assigned_col); G = (A.*assigned_row); ./main_Heffter_Systems.m0000644000175000017500000000260214525730762017522 0ustar cloudconvertcloudconvert% This code constructs the Relative Heffter systems with % respect to the parameters specified below. % Moreover, it constructs the array containing the two orthogonal % Heffter systems. Finally, it also tries to construct the % classical heffters, in order to reduce the possible spectrum % of the strictly weak Heffter arrays. % The output of the code is a subset of the classical Heffters % that can be constructed with the set of parameters, and % the set of stricly weak Heffter arrays (if they exists) with % a possibly empty subset of the remaining classical Heffter arrays. clear all close all clc n = 4; % Dimension of the array % (implemented for n in {3,4}) t = 6; % Dimension of the subgroup k = 3; % Number of filled cells (the current implementation % works exclusively for k = 3) if n==3 H = Heffter_systems_n_3(n,k,t); elseif n==4 H = Heffter_systems_n_4(n,k,t); endif disp('Possible weak Heffter arrays:') jj = 0; j = 0; classical_heffter = []; possibly_strict_heffter = []; for i = 1:length(H) [A,B] = test_strictly_weak1(H{i},2*n*k+t); if norm(A - ones(n))==0 jj = jj+1; classical_heffter{jj} = B; else j = j+1; possibly_strict_heffter{j} = abs(B); endif endfor classical_heffter possibly_strict_heffter ./Heffter_systems_n_4.m0000644000175000017500000001155414525730550017317 0ustar cloudconvertcloudconvertfunction H = Heffter_systems_n_4(n,k,t) v = 2*n*k+t; % Dimension of the group Sym = 1:v/2; % Symbols of an half set % Minus the subgroup of size t aux = find(mod(Sym,v/t)==0); Sym(aux) = []; Triples = zero_sum_triples(Sym,v); % Zero-sum triples in Sym % Without loss of generality, we assume that the first row and the first % column contain the element 1 (or -1) aux1 = Triples(:,1); pos = find(aux1==1); A1 = Triples(pos,:); pos = find(aux1~=1); A2 = Triples(pos,:); A3 = A2; A4 = A2; % When two zero sum triples of A2 are compatibles? A_int = zeros(size(A2)); for i = 1:size(A2,1) for j = i+1:size(A2,1) if length(intersect(A2(i,:), A2(j,:)))==0 A_int(i,j) = 1; endif endfor endfor A_int = A_int+A_int'; trovati = 0; noniso = 0; database = []; for i1 = 1:size(A1,1) b1 = A1(i1,:); % First subset of Heffter system for i2 = 1:size(A2,1) b2 = A2(i2,:); % Second subset of Heffter system G = [b1, b2]; index2 = find(A_int(i2,:)); % search the third subset between % the compatible ones if length(unique(G)) ==length(G) for i3 = 1:size(A3(index2,:),1) b3 = A3(index2(i3),:); % Third subset of Heffter system G = [b1, b2,b3]; index3 = intersect(index2,find(A_int(index2(i3),:))); if length(unique(G)) ==length(G) for i4 = 1:size(A4(index3,:),1) b4 = A4(index3(i4),:); G = [b1, b2,b3,b4]; index4 = intersect(index3,find(A_int(index3(i4),:))); if length(unique(G)) ==length(G) G = [b1; b2;b3;b4]; trovati = trovati+1; new_Heffter_System = true; if noniso>0 % Is this a new Heffter system, or is it an old one? for ijk = 1:length(database) Old_Heffter = database{ijk}; % order the rows based on their smallest element; for row_index = 1:size(G,1) G(row_index,:) = sort(G(row_index,:)); Old_Heffter(row_index,:) = sort(Old_Heffter(row_index,:)); endfor [~,idG] = sort(G(:,1)); [~,idOld] = sort(Old_Heffter(:,1)); Old_Heffter = Old_Heffter(idOld,:); G = G(idG,:); % Check if every row contains the same elements: if norm(G - Old_Heffter)==0 new_Heffter_System = false; endif ## row_same_el = true; ## for row_index = 1:size(G,1) ## if max(abs(sort(G(row_index,:)) - sort(Old_Heffter(row_index,:))))~=0 ## row_same_el = false ; ## endif ## endfor endfor if new_Heffter_System %(row_same_el == false) noniso = noniso+1; database{noniso} = G; endif else noniso = noniso+1; database{noniso} = G; endif endif endfor endif endfor endif endfor endfor disp('Heffter systems for these parameters:') database % These are all the Heffter systems on the set of % symbols Sym % Can we find two Heffter Systems inside of database that are % orthogonal? mm = length(database); num_orthogonal = 0; H = []; for i = 1:mm A1 = database{i}; % Fix one Heffter system for j = i+1:mm A2 = database{j}; % And the second one orthogonal = true; for k1 = 1:size(A1,1) % And now check if they are orthogonal for k2 = 1:size(A2,1) if length(intersect(A1(k1,:),A2(k2,:)))>1 orthogonal = false; endif endfor endfor if orthogonal % If they are orthogonal, construct the array Heff_array = isHeffter(A1,A2); % Before adding the array to the database, check if it is already there isnew = true; Heff_array1 = Heff_array(:,1); [~,idx1] = sort(Heff_array1); Heff_array = Heff_array(idx1,:); for kk = 1:length(H) C = H{kk}; C1= C(:,1); % As before, check up to a permutation of the rows if max(abs(sort(Heff_array1) - sort(C1))) == 0 [~,idx2] = sort(C1); C = C(idx2,:); endif if norm(C - Heff_array)==0 isnew = false; endif endfor if isnew num_orthogonal = num_orthogonal + 1; H{num_orthogonal} = Heff_array; endif endif endfor endfor