Water retention on mathematical surfaces


Water retention on mathematical surfaces is the catching of water in ponds on a surface of cells of various heights on a regular array such as a square lattice, where water is rained down on every cell in the system. The boundaries of the system are open and allow water to flow out. Water will be trapped in ponds, and eventually all ponds will fill to their maximum height, with any additional water flowing over spillways and out the boundaries of the system. The problem is to find the amount of water trapped or retained for a given surface. This has been studied extensively for two mathematical surfaces: magic squares and random surfaces. The model can also be applied to the triangular grid.

Magic squares

have been studied for over 2000 years. In 2007, the idea of studying the water retention on a magic square was proposed. In 2010, a competition at Al Zimmermann's Programing Contests produced the presently known maximum retention values for magic squares order 4 to 28. Computing tools used to investigate and illustrate this problem are found here.
There are 4,211,744 different retention patterns for the 7×7 square. A combination of a lake and ponds is best for attaining maximum retention. No known patterns for maximum retention have an island in a pond or lake.
Maximum-retention magic squares for orders 7-9 are shown below:
The figures below show the 10x10 magic square. Is it possible to look at the
patterns above and predict what the pattern for maximum retention for
the 10x10 square will be? No theory has been developed that
can predict the correct combination of lake and ponds for all orders, however some principles do apply.
The first color-coded figure
shows a design principle of how the largest available numbers are placed around
the lake and ponds. The second and third figures
show promising patterns that were tried but did not achieve
maximum retention.
150664686547774483
536897917840
67989676
58939275
859956
55958982
719010079
7088878347
43737294846542
257496962818039615

145795387835572273
518095897431
78909473
48979141
8582
8688
66999658
70989275
1871100937750
244694781846376354

Several orders have more than one pattern for maximum retention. The figure below shows the two patterns for the 11x11 magic square with the apparent maximum retention of 3,492 units:
155816910347836499672
598910611110210048
8211911798
7310711210168
10412184
10510875
7410912090
861151149665
779111611894
68792113110979544
46271857279886393513

13697698674648990623
68991011081099253
981181169150
7710011311782
8712111470
79105104
75106102
8812011057
769610711983
18951111151128565
416939473801037884442

The most-perfect magic squares require all ^2 or in this case all 121 2x2 planar subsets to have the same sum..
Areas completely surrounded by larger numbers are shown with a blue background.
Before 2010 if you wanted an example of a magic square larger than 5×5 you had to follow clever construction rules that provided very isolated examples. The 13x13 pandiagonal magic square below is such an example. Harry White's CompleteSquare Utility allows anyone to use the magic square as a potter would use a lump of clay. The second image shows a 14x14 magic square that was molded to form ponds that write the 1514 - 2014 dates. The animation notes how the surface was sculptured to fill all ponds to capacity before the water flows off the square. This square honors the 500th anniversary of Durer's famous magic square in Melencolia I.

This figure also provides an example of a square and its complement that have the same pattern of retention.
There are 137 order 4 and 3,254,798 order 5 magic squares that do not retain water.
2121982002022042062081312108642210
27186174176178180182393836343230184199
25511641541561581606160585654162175201
23497114613814014279787674144155177203
21476987132126128939290130139157179205
1945678599122118103102120127141159181207
1743658397107116109114119129143161183209
1541638195105111113115121131145163185211
2151891671491351251121171101019177593711
217191169151137106108123124104897557359
2191931711539610098133134136947355337
221195173828886841471481501528053315
223197647270686616516616817017262293
225425250484644187188190192194196401
1628262422201821321421621822022222414

16 x 16 associative magic square retaining 17840 units. The lake in the first image looks a little uglier than common. Jarek Wroblewski notes that good patterns for maximum retention will have equal or near equal number of retaining cells on each peripheral edge The second image is doctored, shading in the top and bottom 37 values.

The figure below is a 17x17 Luo-Shu format magic square.
The Luo-Shu format construction method seems to produce a maximum number of ponds. The drainage path for the cell in green is long eventually
spilling off the square at the yellow spillway cell.
The figure to the right shows what information can be derived from looking at the actual water content for each cell.
Only the 144 values are highlighted to keep the square from looking too busy.
Focusing on the green cell with a base value 7, the highest obstruction on the path out is its neighbor cell
with the value of 151. Water rained into this cell exits the square at the yellow 10 cell.
13728212126610525089234732185720241186251709
10138283267251235219203187154
15513928426825223622020417127
28156140285269253237221188172
17315714128627025423820518945
46174158142287271255222206190
19117515914328827223922320763
64192176160144289256240224208
20919317716114527325724122581
82210194178162146274258242226
22721119517916314727525924399
100228212196180164148276260244
245229213197181165149277261117
118246230214198182166150278262
263247231215199183167151279135
1362642482322162001841687152280
28112026510424988233722175620140185241698153

00
128
127128
127128127
127127128127
127127128127127
127127127128127127
127127127128127127127
127127127127127127127
127127127127127127
127127127127127
127127127127
127127127
127127
127
00

Mario Mamzeris invented his own method for constructing odd order magic squares. His Order 19 associative magic square is shown below.
The computer age now allows for the exploration of the physical properties of magic squares of any order. The figure below shows the largest magic square studied in the contest. For L > 20 the number of variables/ equations increases to the point where it makes the pattern for maximum retention predictable.
This is a 32x32 panmagic square. Dwane Campbell using binary construction methods produced this interesting water retention example. The GET TYPE utility applied to this square shows that it has the following properties: 1) normal magic 2) pandiagonal 3) bent diagonal two way 4) self-complement.

Random surfaces

Another system in which the retention question has been studied is a surface of random heights. Here one can map the random surface to site percolation, and each cell is mapped to a site on the underlying graph or lattice that represents the system. Using percolation theory, one can explain many properties of this system. It is an example of the invasion percolation model in which fluid is introduced in the system from any random site.
In hydrology, one is concerned with runoff and formation of catchments. The boundary between different drainage basin forms a drainage divide with a fractal dimension of about 1.22.
The retention problem can be mapped to standard percolation.
For a system of five equally probable levels, for example, the amount of water stored R5 is just the sum of the water stored in two-level systems R2 with varying fractions of levels p in the lowest state:
Typical two-level systems 1,2 with p = 0.2, 0.4, 0.6, 0.8 are shown on the right. The net retention of a five-level system is the sum of all these. The top level traps no water because it is far above the percolation threshold for a square lattice, 0.592746.
The retention of a two-level system R2 is the amount of water connected to ponds that do not touch the boundary of the system. When p is above the critical percolation threshold p c, there will be a percolating cluster or pond that visits the entire system. The probability that a point belongs to the percolating or "infinite" cluster is written as P∞ in percolation theory, and it is related to R2 by R2/L2 = p − P∞ where L is the size of the square. Thus, the retention of a multilevel system can be related to a well-known quantity in percolation theory.
To measure the retention, one can use a flooding algorithm in which water is introduced from the boundaries and floods through the lowest spillway as the level is raised. The retention is just the difference in the water level that a site was flooded minus the height of the terrain below it.
Besides the systems of discrete levels described above, one can make the terrain variable a continuous variable say from 0 to 1. Likewise, one can make the surface height itself be a continuous function of the spatial variables. In all cases, the basic concept of the mapping to an appropriate percolation system remains.
A curious result is that a square system of n discrete levels can retain more water than a system of n+1 levels, for sufficiently large order L > L*. This behavior can be understood through percolation theory, which can also be used to estimate L* ≈ −ν where ν = 4/3, p = i*/n where i* is the largest value of i such that i/n < pc, and pc = 0.592746 is the site percolation threshold for a square lattice. Numerical simulations give the following values of L*, which are extrapolated to non-integer values. For example, R2 < R3 for L ≤ 51, but R2 > R''3 for L ≥ 52:
nn+1L*Retention at L*
2351.12790
45198.126000
78440.3246300
910559.1502000
12131390.6428850
14151016.32607000

As n gets larger, crossing become less and less frequent, and the value of L* where crossing occurs is no longer a monotonic function of n.
The retention when the surface is not entirely random but correlated with a Hurst exponent H is discussed in.

Algorithms

The following time line shows the application of different algorithms that have expanded the size of the square that can be evaluated for retention
2007 Define all neighbor-avoiding walks from each interior cell to the exterior and then sort all those paths for the least obstruction or cell value. The least obstruction value minus the interior cell value provides the water retention for that interior cell. The number of neighbor-avoiding walks to be evaluated grows exponentially with the square size and thus limits this methodology to L < 6.
2009 Flooding algorithm - water is introduced from the boundaries and floods through the lowest spillway as the level is raised. The retention is just the difference in the water level that a site was flooded minus the height of the terrain below it. The flooding algorithm allows for the evaluation of water retention up to L < 10,000. This algorithm is similar to Meyer's flooding algorithm that has been used in analysis of topographical surfaces.
2011 With the realization that an n-level system can be broken down into a collection of two-level systems with varying probabilities, standard percolation algorithms can be used to find the retention as simply the total number of sites at the lower level minus the draining regions. A novel application of the Hoshen-Kopelman algorithm in which both rows and columns are added one at a time allows L to be very large, but computing time considerations limits L to the order of 107.
Paths that drain water off the square, used in the neighbor-avoiding walk algorithm
The panel below from left to right shows: 1) the three unique interior positions for the 5×5 square; 2 & 4) correct paths off the square in grey for the interior corner cell in red; 3) incorrect path in grey as the water cannot travel on the diagonals; 5) this path is correct but there is a short-circuit possible between the grey cells. Neighbor-avoiding walks define the unique or non-redundant paths that drain water off the square.