Archive

Posts Tagged ‘C’

Counting the Possible Orderings of Pairwise Multiplication

February 12th, 2014

Suppose we are given n distinct positive real numbers \(a_1 > a_2 > \cdots > a_n > 0\). The question we are going to consider in this post is as follows:

Question. How many different possible orderings are there of the \(n(n+1)/2\) numbers \(\{a_ia_j\}_{1\leq i\leq j\leq n}\)?

To help illustrate what we mean by this question, consider the n = 2 case, where \(a_1 > a_2 > 0\). Then the 3 possible products of \(a_1\) and \(a_2\) are \(a_1^2, a_2^2, a_1a_2\), and it is straightforward to see that we must have \(a_1^2 > a_1a_2> a_2^2\), so there is only one possible ordering in the n = 2 case.

In the n = 3 case, we have \(a_1 > a_2 > a_3 > 0\) and 6 possible products: \(a_1^2, a_2^2, a_3^2, a_1a_2, a_1a_3, a_2a_3\). Some relationships between these 6 numbers are immediate, such as \(a_1^2 > a_1a_2 > a_1a_3 > a_2a_3 > a_3^2\). However, it could be the case that either \(a_2^2 > a_1a_3\) or \(a_1a_3 > a_2^2\) (we ignore the degenerate cases where two products are equal to each other), so there are two different possible orderings in this case:

\(a_1^2 > a_1a_2 > a_2^2 > a_1a_3 > a_2a_3 > a_3^2\quad\text{ or }\\ a_1^2 > a_1a_2 > a_1a_3 > a_2^2 > a_2a_3 > a_3^2.\)

In this post, we will consider the problem of how many such orderings exist for larger values of n. This problem arises naturally from a problem in quantum entanglement: the number of such orderings is exactly the minimum number of linear matrix inequalities needed to characterize the eigenvalues of quantum states that are “PPT from spectrum” [1].

A Rough Upper Bound

We now begin constructing upper bounds on the number of possible orderings of \(\{a_ia_j\}_{1\leq i\leq j\leq n}\). Since we are counting orderings between \(n(n+1)/2\) numbers, a trivial upper bound is given by \((n(n+1)/2)!\), since that is the number of possible orderings of \(n(n+1)/2\) arbitrary numbers. However, this quantity is a gross overestimate.

We can improve this upper bound by creating an \(n \times n\) matrix whose \((i,j)\)-entry is \(a_ia_j\) (note that this matrix is symmetric, positive semidefinite, and has rank 1, which is roughly how the connection to quantum entanglement arises). For example, in the n = 4 case, this matrix is as follows:

\(\begin{bmatrix}a_1^2 & a_1a_2 & a_1a_3 & a_1a_4 \\ * & a_2^2 & a_2a_3 & a_2a_4 \\ * & * & a_3^2 & a_3a_4 \\ * & * & * & a_4^2\end{bmatrix},\)

where we have used asterisks (*) to indicate entries that are determined by symmetry. The fact that \(a_1 > a_2 > \cdots > a_n > 0\) implies that the rows and columns of the upper-triangular part of this matrix are decreasing. Thus we can get an upper bound to the solution to our problem by counting the number of ways that we can place the numbers \(1, 2, \ldots, n(n+1)/2\) (exactly once each) in the upper-triangular part of a matrix in such a way that the rows and columns of that upper-triangular part are decreasing. For example, this can be done in 2 different ways in the n = 3 case:

\(\begin{bmatrix}6 & 5 & 4 \\ * & 3 & 2 \\ * & * & 1\end{bmatrix} \quad \text{and} \quad \begin{bmatrix}6 & 5 & 3\\ * & 4 & 2\\ * & * & 1\end{bmatrix}.\)

The matrix above on the left corresponds to the case \(a_1a_3 > a_2^2\) discussed earlier, while the matrix above on the right corresponds to the case \(a_2^2 > a_1a_3\).

A formula for the number of such ways to place the integers \(1, 2, \ldots, n(n+1)/2\) in a matrix was derived in [2] (see also A003121 in the OEIS), which immediately gives us the following upper bound on the number of orderings of the products \(\{a_ia_j\}_{1\leq i\leq j\leq n}\):

\(\displaystyle(n(n+1)/2)! \frac{1! 2! \cdots (n-1)!}{1! 3! \cdots (2n-1)!}.\)

For n = 1, 2, 3, …, this formula gives the values 1, 1, 2, 12, 286, 33592, 23178480, …

A Better Upper Bound

Before improving the upper bound that we just presented, let’s first discuss why it is not actually a solution to the original question. In the n = 4 case, our best upper bound so far is 12, since there are 12 different ways to place the integers \(1,2,\ldots,10\) in the upper-triangular part of a \(4 \times 4\) matrix such that the rows and columns of that upper-triangular part are decreasing. However, one such placement is as follows:

\(\begin{bmatrix}10 & 9 & 7 & 6 \\ * & 8 & 5 & 3 \\ * & * & 4 & 2 \\ * & * & * & 1\end{bmatrix}.\)

The above matrix corresponds to the following inequalities in terms of \(\{a_ia_j\}_{1\leq i\leq j\leq n}\):

\(a_1^2 > a_1a_2 > a_2^2 > a_1a_3 > a_1a_4 > a_2a_3 > a_3^2 > a_2a_4 > a_3a_4 > a_4^2.\)

The problem here is that there actually do not exist real numbers \(a_1 > a_2 > a_3 > a_4 > 0\) that satisfy the above string of inequalities. To see this, notice in particular that we have the following three inequalities: \(a_2^2 > a_1a_3\), \(a_1a_4 > a_2a_3\), and \(a_3^2 > a_2a_4\). However, multiplying the first two inequalities together gives \(a_1a_2^2a_4 > a_1a_2a_3^2\), so \(a_2a_4 > a_3^2\), which contradicts the third inequality.

More generally, there can not be indices \(i,j,k,\ell,m,n\) such that we simultaneously have the following three inequalities:

\(a_ia_j > a_ka_\ell\), \(a_\ell a_m > a_j a_n\), and \(a_i a_m < a_k a_n\).

I am not aware of a general formula for the number integer matrices that do not lead to these types of “bad” inequalities, but I have computed this quantity for n ≤ 7 (C code is available here), which gives the following better upper bound on the number of possible orderings of the products \(\{a_ia_j\}_{1\leq i\leq j\leq n}\) for n = 1, 2, 3, …: 1,1,2,10,114,2612,108664, …, which we see is significantly smaller than the upper bound found in the previous section for n ≥ 5.

This Bound is Not Tight

It is straightforward to write a script that generates random numbers \(a_1 > a_2 > \cdots > a_n > 0\) and determines the resulting ordering of the pairwise products \(\{a_ia_j\}_{1\leq i\leq j\leq n}\). By doing this, we can verify that the upper bounds from the previous section are in fact tight when n ≤ 5. However, when n = 6, we find that 4 of the 2612 potential orderings do not seem to actually be attained by any choice of \(a_1 > a_2 > \cdots > a_6 > 0\). One of these “problematic” orderings is the one that arises from the following matrix:

\(\begin{bmatrix}21 & 20 & 19 & 18 & 17 & 11\\ * & 16 & 15 & 14 & 10 & 6\\ * & * & 13 & 12 & 8 & 5\\ * & * & * & 9 & 7 & 3\\ * & * & * & * & 4 & 2\\ * & * & * & * & * & 1\end{bmatrix}\)

The problem here is that the above matrix implies the following 5 inequalities:

\(a_1a_5 > a_2^2, \quad \ \ a_2a_4 > a_3^2, \quad \ \ a_2a_5 > a_4^2, \quad \ \ a_3a_4 > a_1a_6, \quad \text{and }\ \ \ a_3a_6 > a_5^2.\)

However, multiplying the first four inequalities gives \(a_1a_2^2a_3a_4^2a_5^2 > a_1a_2^2a_3^2a_4^2a_6\), so \(a_5^2 > a_3a_6\), which contradicts the fifth inequality above. We can similarly prove that the other 3 seemingly problematic orderings are in fact not attainable, so there are exactly 2608 possible orderings in the n = 6 case.

I haven’t been able to compute the number of orderings when n ≥ 7, as my methods for obtaining upper and lower bounds are both much too slow in these cases. The best bounds that I have in the n = 7 case say that the number of orderings is between 50900 and 108664, inclusive.

Update [Feb. 13, 2014]: Giovanni Resta has improved the lower bound in the n = 7 case to 107498, which narrows the n = 7 region down considerably. I’ve also improved the upper bound to 108146 (see this improved version of the C script). In all likelihood, 107498 is the correct number of orderings in this case, and it’s the upper bound 108146 that needs to be further improved.

Update [Feb. 14, 2014]: This sequence is now in the OEIS. See A237749.

Update [Feb. 18, 2014]: Hans Havermann has found a couple of references that talk about this problem (in the language of Golomb rulers) and compute all values for n ≤ 7. See [3] and [4].

References

  1. R. Hildebrand. Positive partial transpose from spectra. Phys. Rev. A, 76:052325, 2007. E-print: arXiv:quant-ph/0502170
  2. R. M. Thrall. A combinatorial problem. Michigan Math. J., 1:81–88, 1952.
  3. M. Beck, T. Bogart, and T. Pham. Enumeration of Golomb rulers and acyclic orientations of mixed graphs. Electron. J. Combin., 19:42, 2012. E-print: arXiv:1110.6154 [math.CO]
  4. T. Pham. Enumeration of Golomb rulers. Master’s Thesis, San Francisco State University, 2011.

On Maximal Self-Avoiding Walks

May 5th, 2009

Given a k × n grid, a self-avoiding walk (SAW) on that grid is a connected path that never touches the same square more than once and never doubles back on itself (note that some sources make the convention that the path is drawn on the edges of the grid from vertex to vertex, but here I will make the convention that the path connects the centres of the squares that the grid forms). I will define a maximal self-avoiding walk to be a self-avoiding walk that touches every square of the grid on which it resides. One natural question that we can ask in this setting is “How many maximal self-avoiding walks are there on a k × n grid?”

Before proceeding, let’s simplify things slightly by making the restriction that the maximal self-avoiding walks must start in the bottom-left corner of the grid (this restriction leaves us with the walks that are known as “Greek-key tours”). Let f(k, n) denote the number of maximal self-avoiding walks on a k × n grid. Unfortunately, finding an expression for f(k, n) in complete generality seems to be out of reach, so we will instead try to answer the question for certain fixed values of k.

Case 1: k = 1
Regardless of n, there is clearly only one maximal self-avoiding walk in this case: a straight line. Thus, f(1, n) = 1 regardless of the value of n.

Case 2: k = 2
It is not difficult to prove (by induction, for example) that f(2, n) = n.

Case 3: k = 3
This is the first case whose solution does not seem trivial. It is well-known (by people who have looked at this problem, anyways) that the number of maximal self-avoiding walks on a 3 × n grid for n = 1, 2, … is 1, 3, 8, 17, 38, … (Sloane’s A046994). This sequence is defined by the following recurrence relations:

Well, from these recurrence relations we can derive the following closed form expression for f(3, n):

It may be worth noting that this formula can be simplified significantly if you consider the case when n is odd separately from the case when n is even, and write f(3, n) as a branch function.

Case 4: k = 4
The number of maximal self-avoiding walks on a 4 × n grid for n = 1, 2, … is 1, 4, 17, 52, 160, … (Sloane’s A046995), but to date no simple closed-form formula for f(4, n) has been found. In 2003, Dean Hickerson proposed the following recurrence relation to define f(4, n), which holds at least for the first 25 terms of the sequence:

While it is possible to derive a closed-form formula for f(4, n) from the above recurrence relation using standard difference equation techniques, the formula is extremely long and cumbersome. One piece of information that we can extract from the closed-form formula (which I won’t write out here) is that f(4, n) ∈ O(2.539n).

Case 5: k ≥ 5
It is now clear that this problem grows very large very quickly, and proceeding in this manner may not be (realistically) feasible. Not much is known about f(k, n) when both k and n are greater than or equal to 5. The best approach in this case is likely that of brute force.

Computing the Number of Maximal SAWs

Here I provide two programs for computing the number of maximal SAWs on a grid of your chosen size. It is recommended that you use the C script rather than the Visual Basic program, as the C script is much faster.

If the Visual Basic file below gives you an error message when you try to run it, you may need to download and install the Visual Basic 6.0 run time files. Click here to download these files. As far as I know, this program should work on Windows 98, ME, 2000, XP and Vista, but I can’t make any guarantees about its compatability.

Download:

Maximal SAW Table of Values

This is a table giving the number of maximal SAWs on a k × n grid. Several of the values in the table below were calculated using the above software — the cells that have “?” in them correspond to values that are currently unknown due to computational limits. Note that there is trivially symmetry across the main diagonal of the table. I apologize for the unreadably small font.

k\n 1 2 3 4 5 6 7 8 9 10 General Term
1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9 10 n
3 1 3 8 17 38 78 164 332 680 1368 Sloane’s A046994
4 1 4 17 52 160 469 1337 3750 10347 28249 Sloane’s A046995
5 1 5 38 160 824 3501 16262 68591 304177 1276805 Sloane’s A145156
6 1 6 78 469 3501 22144 144476 899432 5585508 34092855 Sloane’s A160240
7 1 7 164 1337 16262 144476 1510446 13506023 132712481 1185979605 Sloane’s A160241
8 1 8 332 3750 68591 899432 13506023 180160012 ? ? ?
9 1 9 680 10347 304177 5585508 132712481 ? ? ? ?
10 1 10 1368 28249 1276805 34092855 1185979605 ? ? ? ?
n × n grid: Sloane’s A145157

Update (August 7, 2024): Jay Pantone, Alexander R. Klotz, and Everett Sullivan have written a great paper that (among other things) significantly expands these results.

Related Links:

Counting Lakes

February 6th, 2009

In Conway’s Game of Life, a lake is a pattern that is a simple closed loop made up of diagonally-adjacent dominoes. It is a fact that lakes are always still lifes and that their number of cells is always a multiple of eight, but no one seems to have calculated the number of distinct (ie. not the same under rotation or reflection) lakes that exist on 8n cells; possibly because it’s not a particularly interesting problem (blasphemy!) or possibly because it’s a rather difficult problem (or most likely a combination of the two).

Indeed, computing an explicit formula for the number of lakes on 8n cells seems to be nigh intractable (although some people disagree). In place of an explicit formula I have simply gone the computer science route and coded a little C program to do the counting. The program’s running time is somewhere in the area of O(4n) since it basically brute-forces the solution by noting that lakes are in 1-1 correspondence with walks on a 2D lattice that have three properties: 1) they turn 90 degrees after each step of length one, 2) they eventually return to the starting position, and 3) they never cross a grid point that they’d previously visited (except on the last step when they return to the start).

The sequence (as far as I have computed it) of the number of lakes on 8n cells for n = 1, 2, 3, … is 1, 0, 1, 1, 4, 7, 31, 98, 446, 1894, 9049, 43151 … (Sloane’s A156228). The C source code is provided below in case you’re interested.

Download:

The two smallest lakes, pond and lake 2: