/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 81-93
The existence of square integer Heffter arrays
Jeffrey H. Dinitz
Department of Mathematics and Statistics, University of Vermont, Burlington, VT 05405, USA
Ian M. Wanless *
School of Mathematical Sciences, Monash University, Vic 3800, Australia
Received 9 June 2016, accepted 21 November 2016, published online 19 February 2017
Abstract
An integer Heffter array H(m, n; s, t) is an m x n partially filled matrix with entries from the set {±1, ±2,..., ±ms} such that i) each row contains s filled cells and each column contains t filled cells, ii) every row and column sums to 0 (in Z), and iii) no two entries agree in absolute value. Heffter arrays are useful for embedding the complete graph K2ms+1 on an orientable surface in such a way that each edge lies between a face bounded by an s-cycle and a face bounded by a t-cycle. In 2015, Archdeacon, Dinitz, Donovan and Yazici constructed square (i.e. m = n) integer Heffter arrays for many congruence classes. In this paper we construct square integer Heffter arrays for all the cases not found in that paper, completely solving the existence problem for square integer Heffter arrays.
Keywords: Heffter array, biembedding. Math. Subj. Class.: 05B20, 05C10
1 Introduction
We begin with the general definition of Heffter arrays [1]. A Heffter array H(m, n; s, t) is an m x n matrix with nonzero entries from Z2ms+1 such that
1.	each row contains s filled cells and each column contains t filled cells,
2.	the elements in every row and column sum to 0 in Z2ms+1, and
3.	for every x e Z2ms+1 \ {0}, either x or —x appears in the array.
* Research supported by ARC grant #DP150100506.
E-mail addresses: jeff.dinitz@uvm.edu (Jeffrey H. Dinitz), ian.wanless@monash.edu (Ian M. Wanless) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
82
Ars Math. Contemp. 13 (2017) 107-123
The notion of a Heffter array H(m, n; s, t) was first defined by Archdeacon in [1]. It is shown there that a Heffter array with a pair of special row and column orderings can be used to construct an embedding of the complete graph K2ms+1 on a surface. This connection is given in the following theorem.
Theorem 1.1 ([1]). Given a Heffter array H(m,n; s,t) with compatible orderings ur of the symbols in the rows of the array and on the symbols in the columns of the array, then there exists an embedding of K2ms+1 on an orientable surface such that every edge is on a face of size s and a face of size t. Moreover, if wr and are both simple, then all faces are simple cycles.
We refer the reader to [1] for the definition of a simple ordering and the definition of compatible orderings. We will not concern ourselves with the ordering problem in this paper and will concentrate on the construction of Heffter arrays. In [4] the ordering problem is addressed in more detail in the case when m = t = 3 and n = s.
A Heffter array is called an integer Heffter array if Condition 2 in the definition of Heffter array above is strengthened so that the elements in every row and every column sum to zero in Z. In [2], Archdeacon et al. study the case where the Heffter array has no empty cells. They show that there is an integer H(m, n; n, m) if and only if m, n > 3 and mn = 0, 3 (mod 4) and in general that there is an H(m, n; n, m) for all m, n > 3.
In this paper we will concentrate on constructing square integer Heffter arrays with empty cells. If the Heffter array is square, then m = n and necessarily s = t. So for the remainder of this paper define a square integer Heffter array H(n; k) to be an n x n partially filled array of nonzero integers satisfying the following:
1.	each row and each column contains k filled cells,
2.	the symbols in every row and every column sum to 0 in Z, and
3.	for every element x G {1, 2,..., nk} either x or — x appears in the array.
In [3] the authors study the case of square integer Heffter arrays H(n; k). The following theorem is from that paper.
Theorem 1.2 ([3]). If an H (n; k) exists, then necessarily
3 ^ k ^ n and nk = 0, 3 (mod 4).
Furthermore, this condition is sufficient except possibly when n = 0 or 3 (mod 4) and k = 1 (mod 4).
It should be noted that [3] also contains partial results when n = 0 or 3 (mod 4) and k = 1 (mod 4). In this paper we will solve those cases completely. Our main result is given in the following theorem.
Theorem 1.3. There exists an integer H (n; k) if and only if
3 ^ k ^ n and nk = 0, 3 (mod 4).
We will prove this theorem by first constructing an H(n; 5) where all the filled cells are contained on 5 diagonals. Then we will add s disjoint H(n; 4) to construct H(n; 5 + 4s) = H(n; k) where k = 1 (mod 4). We begin in Section 2 by giving a general construction for H(n; 4) where all of the filled cells are contained in 4 diagonals. In Section 3 we discuss the case when n = 3 (mod 4) and in Section 4 we discuss the case when n = 0 (mod 4).
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays
83
2 H(n; 4) using two sets of consecutive diagonals
An important concept in the prior work on Heffter arrays has been the notion of a shiftable Heffter array. A shiftable Heffter array Hs(n; k) is defined to be a Heffter array H(n; k) where every row and every column contain equal numbers of positive and negative entries. Let A be a shiftable array and x a nonnegative integer. If x is added to each positive element and —x is added to each negative element, then all of the row and column sums remain unchanged. Let A ± x denote the array where x is added to all the positive entries in A and —x is added to all the negative entries.
If A is an integer array, define the support of A as the set containing the absolute value of the elements contained in A. So if A is shiftable with support S and x a nonnegative integer, then A ± x has the same row and column sums as A and has support S + x. In the case of a shiftable Heffter array Hs(n; k), the array Hs(n; k) ± x will have row and column sums equal to zero and support S = {1 + x, 2 + x,..., nk + x}.
In this section we describe an easy construction of a shiftable H(n; 4) where all of the filled cells are contained in two pairs of adjacent diagonals. If H is an n x n array with rows and columns labeled 1,..., n, for i = 1,..., n define the i-th diagonal A to be the set of cells A = {(¿, 1), (i + 1,2),..., (i — 1, n)} where all arithmetic is performed in Zn (using the reduced residues {1,2,..., n}). We say that the diagonals A and Di+1 are consecutive diagonals. We should note that in [3] there is a construction of a shiftable H(n; 4) for all n > 4 that uses 4 consecutive diagonals.
All the constructions in this paper are based on filling in the cells of a fixed collection of diagonals. To aid in these constructions we define the following procedure for filling a sequence of cells on a diagonal. It is termed diag and it has six parameters.
In an n x n array A the procedure diag (r, c, s, A1, A2, installs the entries
A[r + iA1, c + iA1] = s + iA2 for i = 0,1,... — 1.
Here all arithmetic on the row and column indices is performed modulo n, where the set of reduced residues is {1, 2,..., n}. The following summarizes the parameters used in the diag procedure:
•	r denotes the starting row,
•	c denotes the starting column,
•	s denotes the starting symbol,
•	A1 denotes how much the row and column are changed at each step,
•	A2 denotes how much the symbol is changed at each step, and
•	I is the length of the chain.
The following example shows the use of the above definition and is also an example of the construction which will be described in Theorem 2.2.
Example 2.1. A shiftable H(11; 4) where the filled cells are contained in two sets of consecutive diagonals.
84
Ars Math. Contemp. 13 (2017) 107-123
The Heffter array H(11; 4) below is constructed via the following procedures:
diag(4,1,1,1, 2, 11); diag(5,1, -2,1, -2,11); diag(4, 7, -23,1, -2,11); diag(5, 7, 24,1, 2,11).
		38	-39				-16	17		
			40	-41				-18	19	
				42	-43				-20	21
1					44	-23				-22
-2	3					24	-25			
	-4	5					26	-27		
		-6	7					28	-29	
			-8	9					30	-31
-33				-10	11					32
34	-35				-12	13				
	36	-37				-14	15			
We point out a few properties of the Heffter array in Example 2.1 which will be useful in the proof of the main theorem of this section. First we note that all of the filled cells are in the two pairs of consecutive diagonals {D4, D5} and {D9, D10} and that the sum of the symbols in the columns of one of the pairs of diagonals is +1 while the other adds to -1. Hence every column adds to 0. The rows are similar except for row 4. In this row the sum of the symbols in D4 and D5 is -21 while the sum of the symbols in D9 and D10 is +21. So all the row sums are 0. It is also apparent that each row and each column contain two positive values and two negative values making this a shiftable array. Finally it is clear that the support of D4 and D5 is {1,2,..., 22} while the support of D9 and D10 is {23,24,..., 44}. We have thus shown that this is indeed a shiftable integer H(11; 4) where all the filled cells are in the two pairs of consecutive diagonals. The following is the main theorem of this section.
Theorem 2.2. For every n > 4 and any two disjoint pairs of consecutive diagonals, there exists a shiftable integer Heffter array H(n; 4) with filled cells contained in the four diagonals.
Proof. Assume that the two pairs of consecutive diagonals are {Da,Da+1} and {Db, Db+1} with b > a +1. We define the square H using the diag procedures as in Example 2.1 above. So let H be constructed from
diag (a, 1,1,1, 2, n),
diag (a + 1,1, -2,1, -2, n),
diag (a, n + a - b +1, -2n - 1,1, -2, n), and
diag (a + 1, n + a - b +1, 2n + 2,1, 2, n).
Clearly diagonal Da is filled from the procedure diag (a, 1,1,1,2, n) while diagonal Da+1 is filled from diag (a + 1,1, -2,1, -2, n). We next note that a cell (i, j) gets filled
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays	85
from the procedure diag (a, n + a — b +1, —2n — 1,1, -2, n) if and only if j — i = (n + a — b +1) — a = n — b +1 = 1 — b (mod n). So cell (b, 1) is filled from this procedure. Since I = n in this procedure we have that every cell in Db is filled. Similarly every cell in Db+1 is filled from the procedure diag (a + 1, n + a — b +1, 2n + 2,1,2, n).
Considering the column sums, we see that in each column the sum of the cells in Da and Da+1 is —1, while the sum of the cells in Db and Db+1 is +1. Hence the sum of the symbols in each column is 0. Similarly, if r = a, then the sum of the cells in row r in Da and Da+1 is +1, while the sum of the cells in row r in Db and Db+1 is —1. So the sum of the symbols in each row r = a is 0. Now consider row a. The symbols from Da,Da+1, Db and Db+1 are 1, — 2n, —2n — 1 and 4n, respectively, and so the symbols in this row also add to 0.
We next check the support of H. We see that the support of diag (a, 1,1,1,2, n) is {1, 3,..., 2n — 1}, while the support of diag (a + 1,1, —2,1, —2, n) is {2,4,..., 2n} so together they cover the symbols {1, 2,..., 2n}. Further, we have that the support of diag (a, n + a — b +1, —2n — 1,1, —2, n) is {2n +1, 2n + 3,..., 4n — 1}, while the support of diag (a + 1, n + a — b + 1, 2n + 2,1, 2, n) is {2n + 2, 2n + 4,..., 4n}, so these two diagonals cover the symbols {2n +1, 2n + 2,..., 4n}. Hence the support of H is the required {1, 2,..., 4n}. Finally it is clear from the construction that each row and each column contains two positive numbers and two negative numbers. Thus we have shown that H is indeed a shiftable integer H(n; 4), as desired.	□
3 H(n ;k) when n = 3 (mod 4) and k = 1 (mod 4)
In this section we first give a direct construction for H(n; 5) with n = 3 (mod 4) where all of the filled cells are on exactly 5 diagonals. We then use Theorem 2.2 repeatedly to construct H(n; k) for all n = 3 (mod 4) with n > 7, and all k = 1 (mod 4) with 5 < k < n — 2.
We begin with an example of the main construction of this section. Hopefully, the reader can see the type of patterns which will exist in the general case.
Example 3.1. An H(11,5).
10	53				24	—33				—54
—36	—9	44				32	—31			
	—45	—8	52				30	—29		
		—37	—7	43				28	—27	
			—46	—6	51				26	—25
—21				—38	— 11	47				23
12	— 13				—42	4	39			
	14	— 15				—50	3	48		
		16	— 17				—41	2	40	
			18	— 19				—49	—5	55
35				20	—22				—34	1
Theorem 3.2. There exists an H(n, 5) for all n = 3 (mod 4) with n > 7.
Proof. Let h = (n + 1)/2 and q = (n — 3)/4. We construct an n x n array H using the
86
Ars Math. Contemp. 13 (2017) 107-123
following procedures. The procedures are labeled A to N.
A diag(h + 1,h + 1,h - 2,1,-1, h - 3); B diag(3, 3, -(n — 3), 1, 1, h — 3);
C	diag(2, 3, 4n, 2,-1, q);
D	diag(3, 2,-(4n + 1), 2,-1,q);
E	diag(3, 4, 5n - 3, 2, -1,q);
F	diag(4, 3,-(3n + 4), 2,-1,q);
G	diag(h +1,h, -(4n - q), 2,1,q);
H	diag(h + 2, h + 1,-(5n - q - 3), 2,1,q);
I	diag(h, h + 1, 4n + q + 1, 2,1,q);
J	diag(h +1,h + 2, 3n + q + 4, 2, 1,q);
K	diag(h + 1, 2, -(n + 2), 1, -2, h - 2);
L	diag(h + 1,1,n + 1, 1, 2, h - 1);
M	diag(1, h + 1, -3n, 1, 2, h - 1);
N	diag(2, h + 1, 3n - 1,1, -2, h - 2);
We also fill the following cells in an ad hoc manner.
H [1,1] = n - 1; H[1, n] = -(5n - 1); H[h, 1] = -(2n - 1); H[n - 1, n - 1] = -(h - 1); H [n, h] = -2n;
H [1, 2] = 5n - 2; H [2,1] = - (3n + 3); H[h, h] = -n; H [n - 1, n] = 5n; H[n, n - 1] = -(3n + 1);
H [1,h] = 2n + 2; H[2, 2] = -(n - 2); H[h, n] = 2n + 1; H [n, 1] = 3n + 2; H [n, n] = 1.
We now prove that the array constructed by the description above is indeed an integer H(n; 5). To aid in the proof we give a schematic picture of where each of the diagonal procedures fills cells (see Figure 1). The first cell in each of these procedures is shaded and we have placed an X in the ad hoc cells. (In this picture we used n = 15, so h = 8 and
q = 3.)
We first check that the rows all add to 0 (in the integers).
Row 1: There are four ad hoc values plus the first value in diagonal M. The sum is
(n - 1) + (5n - 2) + (2n + 2) - 3n - (5n - 1) = 0.
Row 2: The sum is -(3n + 3) - (n - 2) + 4n + (3n - 1) - (3n - 2) = 0.
Rows 3 to h - 1: First notice that in all of these rows the sum of the N and the M diagonal cells is +1 so we must show that the sum of the three cells in the three center diagonals is -1. There are two cases depending on whether the row r is odd or even. If r is odd, then write r = 3 + 2k where 0 < k < q - 1. Notice that from the D, B and E diagonal cells we get the following sum: -(4n +1) - k - (n - 3) +
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays
87
X	X						X	M						X
X	X	C						N	M					
	D	B	E						N	M				
		F	B	C						N	M			
			D	B	E						N	M		
				F	B	C						N	M	
					D	B	E						N	M
X						F	X	I						X
L	K						G	A	J					
	L	K						H	A	I				
		L	K						G	A	J			
			L	K						H	A	I		
				L	K						G	A	J	
					L	K						H	X	X
X						L	X						X	X
Figure 1: Construction in Theorem 3.2 for n = 15.
2k + (5n — 3) — k = —1 as desired. If r is even, then write r = 4 + 2k where 0 < k < q — 2. From the F, B and C diagonal cells we get the following sum:
—	(3n + 4) — k — (n — 3) + 1 + 2k + 4n — 1 — k = —1, as desired.
Row h: There are three ad hoc values plus the last of the F diagonal as well as the first of the I diagonal. We get the row sum: — (2n — 1) — n + (2n + 1) — (3n + 4) — (q —
1)	+4n + q +1=0.
Rows h+1 to n — 2: Note that in all of these rows the sum of the L and the K diagonal cells is — 1 so we must show that the sum of the three cells in the three center diagonals is +1. There are again two cases depending on whether the row r is odd or even. If r is odd, noting that h is even, we write r = (h + 1) + 2k where 0 < k < q — 1. Now, from the G, A and J diagonal cells we get the following sum: — (4n — q) + k + (h —
2)	— 2k +(3n+q+4) + k = —n+2q + h+2 = 1. If r is even, writer = (h + 2)+2k where 0 < k < q — 2. From the H, A and I diagonal cells we get the following sum:
—	(5n — q — 3) + k + (h — 3) — 2k + (4n + q + 2) + k = —n + 2q + h + 2=1.
Row n — 1 : We add the values in diagonals L, K and H with two ad hoc values to get:
(n + 1) + 2(h — 3) — (n + 2) — 2(h — 3) — (5n — q — 3) + (q — 1) — (h — 1) + 5n = —h + 2q + 2 = 0.
Rown: Thesumis (3n + 2) — 2n — (3n +1) + 1 + (n +1) + 2(h — 2) = —n + 2h — 1 = 0. So all rows add to zero. Next we check that the columns also all add to zero.
Column 1: There are four ad hoc values plus the first value in diagonal L. The sum is
(n — 1) — (3n + 3) — (2n — 1) + (n + 1) + (3n + 2) = 0.
Column 2: The sum is 5n — 2 — (n — 2) — (4n +1) — (n + 2) + (n + 1) + 2 = 0.
88
Ars Math. Contemp. 13 (2017) 107-123
Columns 3 to h — 1: Note that in all of these columns the sum of the L and the K diagonal cells is +1 so we must show that the sum of the three cells in the three center diagonals is —1. There are two cases depending on whether the column c is odd or even. If c is odd, then write c = 3 + 2k where 0 < k < q — 1. From the C, B and F diagonal cells we get the following sum: 4n — k — (n — 3) + 2k — (3n + 4) — k = —1. If c is even, then write c = 4 + 2k where 0 < k < q — 2. From the E, B and D diagonal cells we get the following sum: (5n — 3) — k — (n — 4) + 2k — (4n +1) — 1 — k = —1, as desired.
Column h: There are three ad hoc values plus the last of the E diagonal as well as the first of the G diagonal. We get (2n + 2) — n — 2n + (5n — 3) — (q — 1) — (4n — q) = 0.
Columns h + 1 to n — 2: In all of these columns the sum of the M and the N diagonal cells is —1, so we must show that the sum of the three cells in the three center diagonals is +1. There are again two cases depending on whether the column c is odd or even. If c is odd, noting that h is even, we write c = (h + 1) + 2k where 0 < k < q — 1. Now, from the I, A and H diagonal cells we get the following sum: (4n + q + 1) + k + (h — 2) — 2k — (5n — q — 3) + k = —n + 2q + h + 2 = 1. If c is even, write c = (h + 2) + 2k where 0 < k < q — 2. From the J, A and G diagonal cells we get the following sum: (3n + q + 4)+ k + (h — 3) — 2k — (4n — q) +1 + k = —n + 2q + h + 2=1.
Column n — 1 : We add the values in diagonals M, N and J with two ad hoc values to get:
(—3n) + 2(h — 3) + (3n — 1) — 2(h — 3) + (3n + q + 4)+ q — 1 — (h — 1) — (3n + 1) = 2q — h + 2 = 0.
Column n: The sum is —5n +1 — 3n + 2(h — 2) + 2n +1 + 5n +1 = —n + 2h — 1 = 0.
So we have shown that all column sums are zero. Next we consider the support of H. We do this by looking at the elements used in each of the diagonals as well as the ad hoc symbols. We will write [u, v](w) if the elements in diagonal W consist of the integers in the closed interval [u, v] and we give the ad hoc symbols individually. Note that we write all the numbers in terms of the value q (where 4q + 3 = n). The support of H is:
{1, [2, 2q](A), 2q + 1, [2q + 2, 4q](B), 4q +1, 4q + 2, 4q + 3, [4q + 4, 8q + 4](K U L),
8q + 5, 8q + 6, 8q + 7, 8q + 8, [8q + 9,12q + 9](m U n), 12q + 10,12q + 11, 12q + 12, [12q + 13, 13q + 12](f), [13q + 13,14q + 12](j), [14q + 13, 15q + 12](g), [15q + 13, 16q + 12](c), [16q + 13, 17q + 12](d), [17q + 13, 18q + 12](i),
[18q + 13,19q + 12](h), [19q + 13, 20q + 12](e), 20q + 13, 20q + 14, 20q + 15}
= [1, 20q +15] = [1, 5n].
We have shown that H is indeed an integer Heffter array H(n; 5).	□
We are now ready to prove the main theorem of this section. Let k = 5 + 4s. To construct an H(n; k) we start with the H(n; 5) constructed in Theorem 3.2 and add s disjoint H(n; 4) (with the symbols shifted accordingly), as constructed in Theorem 2.2. The details are given in the following theorem.
Theorem 3.3. There exists an integer Heffter array H(n; k) for all n = 3 (mod 4) and k = 1 (mod 4) with n ^ 7 and 5 ^ k ^ n — 2.
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays
89
Proof. Again let h = (n + 1)/2, noting that h is necessarily even, and let k = 5 + 4s. When s = 0 we are done by Theorem 3.2. So we assume that s > 1, and hence that 4 < 4s < n—7. Begin with H = H(n; 5) constructed in Theorem 3.2. We place s (shifted) H(n; 4) constructed in Theorem 2.2 in 4s empty diagonals of H. These empty diagonals will come in pairs of consecutive diagonals. Specifically, for each 0 < t < s — 1 place Ht = H(n; 4) ± (5n + 4nt) on the 4 diagonals £3+24, £4+24, Dh+2+2t, and Dh+3+2t.
A few things need to be checked. The filled diagonals in H are Di, D2, Dh, Dh+i, and Dn. The diagonals that get filled with the Ht's are D3, D4,..., D1+2s, D2+2s and Dh+2, Dh+3,..., Dh+2s, Dh+2s+1. Since 4s < n — 7, then 2s + 2 < h — 2 and also h + 2s + 1 < n — 2. So the filled diagonals in H, H1, H2,..., Hs are all disjoint.
The row and column sums in H as well as in each Ht, 0 < t < s — 1 is zero, hence the resulting array has row and column sum zero. Finally, note that the support of H is [1, 5n] and for each Ht the support is [5n + 4nt + 1, 5n + 4nt + 4n] = [5n + 4nt + 1, 9n + 4nt]. So the support in the final array is
s — 1
[1, 5n] U (J [5n + 4nt +1, 9n + 4nt]
t=0
= [1, 5n] U [5n + 1, 9n] U [9n + 1, 13n] U • • • U [5n + 4n(s — 1) + 1, 9n + 4n(s — 1)].
Since 9n + 4n(s — 1) = n(5 + 4s) = nk, the support is [1,nk], completing the proof.	□
4 H(n ;k) when n = 0 (mod 4) and k = 1 (mod 4)
This section follows the same structure as Section 3. We first give a direct construction for H(n; 5) with n = 0 (mod 4) where all of the filled cells are on exactly 5 diagonals. We then use Theorem 2.2 repeatedly to construct H(n; k) for all n = 0 (mod 4) with n > 8, and all k = 1 (mod 4) with 5 < k < n — 3. We again begin with an example of the main construction of this section.
Example 4.1. An H(16,5).
46	— 14	62						—49	—45						
	—63	— 13	75						44	—43					
		—50	— 12	61						42	—41				
			—64	— 11	74						40	—39			
				—51	— 10	60						38	—37		
					—65	—9	73						36	—35	
						—52	—8	59						34	—33
—30							—66	77	67						—48
15	— 16							—58	6	53					
	17	— 18							—72	5	68				
		19	—20							—57	4	54			
			21	—22							—71	3	69		
				23	—24							—56	2	55	
					25	—26							—70	—7	78
—32						27	80							—47	—28
1	76						—79	—29							31
90
Ars Math. Contemp. 13 (2017) 107-123
Theorem 4.2. There exists an H(n, 5) for all n = 0 (mod 4) with n > 8.
Proof. Let h = n/2 and q = n/4. We construct an n x n array H using the following procedures. The procedures are labeled A to N.
A diag(h +1,h + 2, h — 2,1, —1, h — 3); B diag(1, 2, —(n — 2), 1, 1, h — 1);
C	diag(1, 3, 4n — 2, 2, —1,q);
D	diag(2, 2, —(4n — 1), 2, —1,q);
E	diag(2, 4, 5n — 5, 2, —1,q — 1);
F	diag(3, 3, —(3n + 2), 2, — 1, q — 1);
G	diag(h + 1, h + 1, —(4n — q — 2), 2,1, q — 1);
H	diag(h + 2, h + 2, —(5n — q — 4), 2,1, q — 1);
I	diag(h, h + 2, 4n + q — 1, 2,1,q — 1);
J	diag(h +1,h + 3, 3n + q + 1, 2, 1,q — 1);
K	diag(h + 1,1,n — 1, 1, 2, h — 1);
L	diag(h + 1, 2, —n, 1, —2, h — 2);
M	diag(2, h + 2, 3n — 4,1, —2, h — 2);
N	diag(1, h + 2, —(3n — 3), 1, 2, h — 1);
We also fill the following cells in an ad hoc manner.
H [1,1] = 3n — 2; H [h, 1] = —(2n — 2); H[h, n] = —3n; H[n — 2, n] = 5n — 2; H[n — 1, h] = 5n; H[n — 1, n] = —(2n — 4);
H[n, 2] = 5n — 4; H[n, h + 1] = —(2n — 3);
H [1,h +1 H[h, h + 1 H[n — 2, n — 1 H [n — 1,1 H [n — 1, n — 1 H [n, 1 H[n, h H[n, n
—	(3n +1); 5n — 3;
—(h — 1); —2n;
—	(3n — 1); 1;
—	(5n — 1); 2n 1.
We now prove that the array constructed by the description above is indeed an integer H(n; 5). To aid in the proof we again give a schematic picture of where each of the diagonal procedures fills cells (see Figure 2). The first cell in each of these procedures is shaded and we have placed an X in the ad hoc cells. (In this picture we used n = 16, so h = 8 and
q = 4.)
We first check that the rows all add to zero.
Row 1: There are two ad hoc values plus the first value in diagonals B, C and N. The sum
is (3n — 2) — (n — 2) + (4n — 2) — (3n +1) — (3n — 3) = 0.
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays
91
X	B	C						X	N						
	D	B	E						M	N					
		F	B	C						M	N				
			D	B	E						M	N			
				F	B	C						M	N		
					D	B	E						M	N	
						F	B	C						M	N
X							D	X	I						X
K	L							G	A	J					
	K	L							H	A	I				
		K	L							G	A	J			
			K	L							H	A	I		
				K	L							G	A	J	
					K	L							H	X	X
X						K	X							X	X
X	X						X	X							X
Figure 2: Construction in Theorem 4.2 for n = 16.
Rows 2 to h — 1: In all of these rows the sum of the N and the M diagonal cells is +1 so we must show that the sum of the three cells in the three center diagonals is — 1. There are two cases depending on whether the row r is odd or even. If r is even, then write r = 2 + 2k where 0 < k < q — 2. From the D, B and E diagonal cells we get the following sum: —(4n — 1) — k — (n — 3) + 2k + (5n — 5) — k = —1. If r is odd, then write r = 3 + 2k where 0 < k < q — 2. Notice that from the F, B and C diagonal cells we get the following sum: — (3n + 2) — k — (n — 4) + 2k + (4n — 3) — k = — 1 as desired.
Row h: The sum is: —(2n — 2) — (4n — 1) — (q — 1) + (5n — 3) + (4n + q — 1) — 3n = 0.
Row h + 1 to n — 3: Note that in all of these rows the sum of the L and the K diagonal cells is — 1 so we must show that the sum of the three cells in the three center diagonals is +1. There are again two cases depending on whether the row r is odd or even. If r is odd, noting that h is even, we write r = (h + 1) + 2k where 0 < k < q — 2. Now, from the G, A and J diagonal cells we get the following sum: — (4n — q — 2) + k + (h — 2) — 2k + (3n + q + 1) + k = —n + 2q + h +1 = 1, as desired. If r is even, write r = (h + 2) + 2k where 0 < k < q — 3. From the H, A and I diagonal cells we get the following sum: —(5n —q — 4)+k+(h —3)—2k+(4n+q) + k = —n+2q+h+1 = 1.
Row n — 2: The sum is: (n — 1) + 2(h — 3) — n — 2(h — 3) — (5n — q — 4) + (q — 2) — h + 1 + (5n — 2) = 2q — h = 0.
Rown—1: Thesumis: —2n+(n—1)+2(h—2)+5n—(3n —1) —(2n—4) = —n+2h = 0.
Row n: The sum is: 1 + (5n — 4) — (5n — 1) — (2n — 3) + (2n — 1) = 0.
So all rows add to zero. Next we check that the columns also all add to zero.
Column 1: There are four ad hoc values plus the first value in diagonal K. The sum is
(3n — 2) — (2n — 2) + (n — 1) — 2n +1 = 0.
93
Ars Math. Contemp. 13 (2017) 107-123
Column 2: The sum is: —(n — 2) — (4n — 1) — n + (n + 1) + (5n — 4) = 0.
Columns 3 to h — 1: Note that in all of these columns the sum of the L and the K diagonal cells is +1, so we must show that the sum of the three cells in the three center diagonals is —1. There are two cases depending on whether the column c is odd or even. If c is odd, then write c = 3 + 2k where 0 < k < q — 2. From the C, B and F diagonal cells we get the following sum: (4n — 2) — k — (n — 3) + 2k — (3n + 2) — k = — 1. If c is even, then write c = 4 + 2k where 0 < k < q — 3. From the E, B and D diagonal cells we get the following sum: (5n — 5) — k — (n — 4)+2k — 4n — k = —1, as desired.
Column h: There are two ad hoc values plus the last of the E, B and D diagonals. We get
5n — (5n — 1) + (5n — 5) — (q — 2) — (n — 2) + (h — 2) — (4n — 1) — (q — 1) = 0.
Column h +1: The sum is: —(3n + 1) + (4n — 2) — (q — 1) + (5n — 3) — (4n — q — 2) — (2n — 3) = 0.
Columns h + 2 to n — 2: In all of these columns the sum of the M and the N diagonal cells is —1, so we must show that the sum of the three cells in the three center diagonals is +1. There are again two cases depending on whether the column c is odd or even. If c is even, noting that h is even, write c = (h + 2) + 2k where 0 < k < q — 2. From the I, A and H diagonal cells we get the following sum: (4n + q — 1) + k + (h — 2) — 2k — (5n — q — 4)+ k = —n + h + 2q +1 = 1. If c is odd, we write c = (h + 3) + 2k where 0 < k < q — 3. Now, from the J, A and G diagonal cells we get the following sum: (3n + q +1) + k + (h — 3) — 2k — (4n — q — 3) + k = —n + 2q + h +1 = 1.
Column n — 1: The sum is: —(3n — 3) + 2(h — 3) + (3n — 4) — 2(h — 3) + (3n + q + 1) + (q — 2) — (h — 1) — (3n — 1) = 2q — h = 0.
Column n: The sum is: —(3n — 3) + 2(h — 2) — 3n + (5n — 2) — (2n — 4) + (2n — 1) = —n + 2h = 0.
So we have shown that all column sums are zero. Next we consider the support of H. We do this by looking at the elements used in each of the diagonals as well as the ad hoc symbols used. We again write [u, v](w) if the elements in diagonal W consist of the integers in the closed interval [u, v] and we give the ad hoc symbols individually. Note that we write all the numbers in terms of the value q (where 4q = n). The support of H is:
{1, [2, 2q — 2](a), 2q — 1, [2q, 4q — 2](b), [4q — 1, 8q — 5](K U l), 8q — 4, 8q — 3, 8q — 2, 8q — 1, 8q, [8q + 1,12q — 3](m U n), 12q — 2, 12q — 1,12q, 12q + 1, [12q + 2,13q](F), [13q + 1, 14q — 1](j), [14q, 15q — 2](g), [15q — 1, 16q — 2](c), [16q — 1,17q — 2](d), [17q — 1,18q — 3](i), [18q — 2,19q — 4](h), [19q — 3, 20q — 5](e), 20q — 4, 20q — 3, 20q — 2, 20q — 1, 20q} = [1, 20q] = [1, 5n].
We have shown that the array H is indeed an integer Heffter array H(n; 5).	□
We now present the main theorem of this section.
Theorem 4.3. There exists an integer Heffter array H(n; k) for all n = 0 (mod 4) and k = 1 (mod 4) with 5 ^ k ^ n — 3.
J. H. Dinitz and I. M. Wanless: The existence of square integer Heffter arrays
100
Proof. The proof is very similar to that of Theorem 3.3. As above, let h = n/2, where h is necessarily even, and let k = 5 + 4s. When s = 0 we are done by Theorem 4.2. So we assume that s > 1, and hence that 4 < 4s < n - 8. Begin with H = H(n; 5) constructed in Theorem 4.2. We place s (shifted) H(n; 4) constructed in Theorem 2.2 in 4s empty diagonals of the H(n; 5). These empty diagonals will again come in pairs of consecutive diagonals. Specifically, for each 0 < t < s - 1 place Ht = H(n; 4) ± (5n + 4nt) on the four diagonals D2+2t, D3+2t, Dh+2+2t, and Dh+3+2t.
A few things need to be checked. The filled diagonals in H are D1, Dh, Dh+1, Dn-1, and Dn. The diagonals that get filled with the Ht's are D2, D3,..., D2s, D1+2s and Dh+2, Dh+3, ..., Dh+2s, Dh+2s+1. Since 4s < n - 8, then 2s + 1 < h - 3 and also h + 2s + 1 < n - 3. So the filled diagonals in H, H1, H2,..., Hs are all disjoint.
The row and column sums in H as well as in each Ht, 0 < t < s - 1 is zero, hence the resulting array has row and column sum zero. Finally, note that the support of H is [1, 5n] and for each Ht the support is [5n + 4nt + 1, 5n + 4nt + 4n] = [5n + 4nt + 1, 9n + 4nt]. So the support in the final array is
s — 1
[1, 5n] U (J [5n + 4nt +1, 9n + 4nt]
t=0
= [1, 5n] U [5n + 1, 9n] U [9n + 1, 13n] U • • • U [5n + 4n(s - 1) + 1, 9n + 4n(s - 1)].
Since 9n + 4n(s - 1) = n(5 + 4s) = nk, the support is [1,nk], completing the proof.	□
5 Conclusion
In the paper [3], it was proven that the necessary conditions for the existence of an integer H(n; k) are that n > k and nk = 0,3 (mod 4). Furthermore, this condition was proved to be sufficient except possibly when n = 0 or 3 (mod 4) and k = 1 (mod 4). In Section 3 we proved that H(n; k) exist when n = 3 (mod 4) and k = 1 (mod 4) and in Section 4 we proved that H(n; k) exist when n = 0 (mod 4) and k = 1 (mod 4). From this we have the main result of this paper.
Theorem 5.1. There exists an integer Heffter array H (n; k) if and only if
3 ^ k ^ n and nk = 0, 3 (mod 4).
In future work we will consider the case when the Heffter array H(n; k) is not an integer Heffter array. In this case the only necessary condition is that 3 < k < n.
References
[1]	D. S. Archdeacon, Heffter arrays and biembedding graphs on surfaces, Electron. J. Combin. 22 (2015), #P1.74.
[2]	D. S. Archdeacon, T. Boothby and J. H. Dinitz, Tight Heffter arrays exist for all possible values, J. Combin. Des. 25 (2017), 5-35, doi:10.1002/jcd.21520.
[3]	D. S. Archdeacon, J. H. Dinitz, D. M. Donovan and E. S. Yazici, Square integer Heffter arrays with empty cells, Des. Codes Cryptogr. 77 (2015), 409-426, doi:10.1007/s10623-015-0076-4.
[4]	D. S. Archdeacon, J. H. Dinitz, A. Mattern and D. R. Stinson, On partial sums in cyclic groups, J. Combin. Math. Combin. Comput. 98 (2016), 327-342.