Water retention on mathematical surfaces

Not to be confused with Wetting § Ideal solid surfaces.
Water being poured over a Lego surface.
Illustration of water retention on a surface.

Water retention on mathematical surfaces refers to the water caught 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.

Magic squares

Retention on a 5x5 magic square.
A 5x5 magic square with the maximal retention.

Magic squares have been studied for over 2000 years. In 2007, the idea of studying the water retention on a magic square was proposed.[1] In 2010, Al Zimmermann's programing contest[2] produced the presently known maximum retention values for magic squares order 4 to 28.[3] Computing tools used to investigate and illustrate this problem are found here.[4][5][6]

There are 4,211,744 different retention patterns for the 7x7 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.[1]

136 units of retention
1 34 36 32 31 39 2
25 20 5 15 14 49 47
24 12 45 28 16 13 37
38 9 27 40 29 11 21
41 8 17 23 46 18 22
43 48 10 7 6 19 42
3 44 35 30 33 26 4
island spillway
365 units of retention
5 33 44 39 34 18 2
20 49 8 15 11 48 24
37 14 23 29 30 6 36
43 12 22 17 26 10 45
38 1 27 21 32 16 40
28 47 9 13 7 46 25
4 19 42 41 35 31 3
lake
405 units of retention
4 25 46 19 31 32 18
27 44 16 45 12 2 29
47 10 14 6 48 20 30
21 43 1 42 5 41 22
33 11 49 3 24 15 40
34 7 13 37 17 39 28
9 35 36 23 38 26 8
pond
417 units of retention
13 30 22 41 39 20 10
31 15 48 7 4 45 25
27 44 17 18 21 8 40
23 42 5 29 9 43 24
34 1 47 6 49 2 36
35 11 3 46 16 38 26
12 32 33 28 37 19 14
best for max retention

Maximum-retention magic squares for orders 7-9 are shown below:[3]

418 units of retention
2 22 38 40 39 19 15
29 45 13124 44 28
42 172021268 41
25 46 10186 43 27
32 3 49 7 48 1 35
31 911 47 16 37 24
14 33 34 30 36 23 5
Hermann Jurksch April 6, 2010
797 units of retention
1 26 41 39 50 47 40 16
36 43 21 61 97 51 32
42 6 62 15 57 255 48
29 58 142327 56 4 49
52 1320332218 64 38
53 1735248 60 19 44
37 63 1211 59 2 46 30
10 34 55 54 28 45 31 3
Hermann Jurksch April 5, 2010
1,408 units of retention
1 37 57 47 66 50 53 55 3
43 59 11 77 25751015 54
58 7 78 213422 81 12 56
45 73 1423323027 74 51
69 17392852363526 67
44 72 1838421320 76 46
64 6 80 163124 79 8 61
40 65 9 70 19 71 4 62 29
5 33 63 49 68 48 60 41 2
Walter Trump June 12, 2010

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.[1]

2267 units of retention
1 41 79 58 75 63 64 68 52 4
47 80 5 81 8 90 87 6 76 25
78 7 35 23 97 44 36 100 13 72
60 82 19 91 39 29 27 14 93 51
73 21 98 32 40 48 33 59 16 85
65 89 46 26 50 62 34 30 20 83
56 88 43 28 31 37 22 42 92 66
70 11 99 17 55 38 45 94 9 67
53 71 12 95 24 10 96 18 77 49'
2 15 69 54 86 84 61 74 57 3
color key:
> > > >
2251 units of retention
150664686547774483
5368179732912547840
67139828352496521676
58931541362151922375
85302934456437269956
55951031634422891482
71209060332710071879
706598819878388347
4373721194129846542
257496962818039615
2228 units of retention
145795387835572273
51802095114089147431
7819904215563394573
4897309642636439141
85285422685761232582
8613396221524660 3888
6699104959 3212249658
709986346717923775
1871161006589377750
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:[3]

Pattern #1
1 55 81 69 103 47 83 64 99 67 2
59 89 13 106 17 111 18 102 8 100 48
82 14 119 364553 117 197612 98
73 107 3143462337 112 30 101 68
104 20566154605238 121 21 84
105 2725508070661649 108 75
74 109 353978584122 120 5 90
86 10 115 57342840 114 26 96 65
77 91 33 116 2932 118 244215 94
6 87 92 9 113 110 11 97 7 95 44
4 62 71 85 72 79 88 63 93 51 3
Pattern #2
1 36 97 69 86 74 64 89 90 62 3
68 99 10 101 8 108 109 1211 92 53
98 53115 118 2858 116 61 91 50
77 100 21 113 22293566 117 9 82
87 6 121 325141723938 114 70
79 105 4633527160474925 104
75 106 5423815556454826 102
88 7 120 674240634334 110 57
76 96 59 107 27303724 119 13 83
18 95 1917 111 115 14 112 20 85 65
4 16 93 94 73 80 103 78 84 44 2

The most-perfect magic squares require all (n-1)^2 or in this case all 121 2x2 planar subsets to have the same sum. ( a few examples flagged with yellow background, red font). Increased internal complexity reduces retention.[7][8]

Before 2010 if you wanted an example of a magic square larger than 5x5 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 [4] 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.

The figure below is a 15x15 bordered magic square with zero water retention.[4] 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.[1]

212 198 200 202 204 206 208 13 12 10 8 6 4 2 210
27 186 174 176 178 180 182 39 38 36 34 32 30 184 199
25 51 164 154 156 158 160 61 60 58 56 54 162 175 201
23 49 71 146 138 140 142 79 78 76 74 144 155 177 203
21 47 69 87 132 126 128 93 92 90 130 139 157 179 205
19 45 67 85 99 122 118 103 102 120 127 141 159 181 207
17 43 65 83 97 107 116 109 114 119 129 143 161 183 209
15 41 63 81 95 105 111 113 115 121 131 145 163 185 211
215 189 167 149 135 125 112 117 110 101 91 77 59 37 11
217 191 169 151 137 106 108 123 124 104 89 75 57 35 9
219 193 171 153 96 100 98 133 134 136 94 73 55 33 7
221 195 173 82 88 86 84 147 148 150 152 80 53 31 5
223 197 64 72 70 68 66 165 166 168 170 172 62 29 3
225 42 52 50 48 46 44 187 188 190 192 194 196 40 1
16 28 26 24 22 20 18 213 214 216 218 220 222 224 14

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 ( in this case 7 cells on each edge) [2] The second image is doctored, shading in the top and bottom 37 values.

The figure below is a 17x17 Luo-Shu format magic square.[9] 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 (151-7=144 units retained). Water rained into this cell exits the square at the yellow 10 cell.

13728212126610525089234732185720241186251709
101382831222671062519023574219582034218726154
155111392841232681072529123675220592044317127
281561214028512426910825392237762216018844172
173291571314128612527010925493238772056118945
461743015814142287126271110255942227820662190
191471753115915143288127272111239952237920763
641924817632160161442891282561122409622480208
209651934917733161171452731292571132419722581
82210661945017834162114627413025811424298226
22783211671955117918163214727513125911524399
100228842126819635180191643148276132260116244
245101229852135219736181201654149277133261117
118246102230692145319837182211665150278134262
26311924786231702155419938183221676151279135
13626410324887232712165520039184231687152280
28112026510424988233722175620140185241698153
00
144144144144144144128
127144144144144144128
127144144144144128127
127127144144144128127
127127144144128127127
127127127144128127127
127127127128127127127
127127127127127127127
127127127144127127127
127127127144144127127
127127144144144127127
127127144144144144127
127144144144144144127
127144144144144144144
144144144144144144144
00

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.

L = 28: 219822 units of retention
1 5 259 659 257 713 712 282 256 283 657 255 656 284 726 725 254 285 654 253 286 55 673 674 471 645 7 3
96406642571726277167157142866829744303173074350681680679515267820664611
265665355722496618714849512172140077441813017629354174947910617538914823068243644
66314724356313513751891984492137758747853913932660451750461566141442638477677276
2667201645723542264911715121177762472445034358562940614463475159246212513451444672
711155651161003575791126377771084694335468055952546852622714675236855732821246671
710161531742221193536277786429745654447417847341056351533140338775340256930445670
70917703251685094457791663664018392482129338408492585529369298424754582519676275
26771915610345553178039135853776142367309522245320437632386545497224123755161675277
264718444600508781196553653524883446241042165519861637029423310141649010975647652
66218723417782310564606420483359518548246475586283855716914922333523586113733274
2636692187831274295817739913688351602538636635371220745709963354349850217348727
66119784407179184195609393495203567360576394384388137625154523229489485219314738279
26874859730750561544131558356219454244635037258831644312016289102560317110329737272
7292052117723234012841115212233424160538336141257820261973611549589587432568736278
26274668580242187558183398601594182373296460349332556205419614323547586207114735273
269745458131111783376105326126223825936555444836261382574172493466126145630734280
2617471584655982214592145241673746085334093193305953481814283054535841996176533651
6602177353656194345165204381621528447211500135452342363301396527185225764306666281
270694517772392431312240375190617151913243335202312155113475402389776341370749650
2606931054057715502953803023363116202341334271975161509060736442576248667530703271
536923001636317703761911575524144155554226265903395077918814776143030843613270254
6832239742353537976915542149432245439021751062310720059118676034134659323711524696
684232281183775753037683275344875734384724575994644391437596041381607239512432697
480691209378440504140501767812011594042104675775716975819342647093596639180701499
64825869529919220848132131876646396635068423623975734370845024317043460370662641
10649386903937689688687407323674274174073973141667357054234137046664312
2 6 647 287 686 685 288 252 251 658 289 728 250 249 290 248 291 655 292 653 56 698 699 700 476 642 8 4
Jarek Wroblewski March 24, 2010

Random surfaces

Water retention on a random surface.
Water retention on a random surface of 10 levels.
Five levels

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.[10][11][12]

In hydrology, one is concerned with runoff and formation of catchments.[13] The boundary between different drainage basin (watersheds in North America) forms a drainage divide with a fractal dimension of about 1.22.[14] [15] [16]

The retention problem can be mapped to standard percolation.[17][18][19] 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(p) with varying fractions of levels p in the lowest state:

R5 = R2(1/5) + R2(2/5) + R2(3/5) + R2(4/5)

Typical two-level systems 1,2 with p = 0.2, 0.4, 0.6, 0.8 are shown on the right (blue: wet, green: dry, yellow: spillways bordering wet sites). 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(p) 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(p) by R2(p)/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* ≈ (p - pc)−ν 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 > R3 for L ≥ 52:[17]

n n+1 L* Retention at L*
2 3 51.12 790
4 5 198.1 26000
7 8 440.3 246300
9 10 559.1 502000
12 13 1390.6 428850
14 15 1016.3 2607000

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.[19]

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 (negative values are set to a retention value of 0). The number of neighbor-avoiding walks to be evaluated grows exponentially with the square size and thus limits this methodology to L < 6.[1]

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.[17] 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 (clusters of low-level sites touching the boundary). 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 (up to 109), but computing time considerations limits L to the order of 107.[20]

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 5x5 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.

00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 1
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00
00 00 00 00 00

See also

References

  1. 1 2 3 4 5 Craig Knecht, http://www.knechtmagicsquare.paulscomputing.com
  2. 1 2 Al Zimmermann http://www.azspcs.net/Contest/MagicWater/FinalReport
  3. 1 2 3 Harvey Heinz, http://www.magic-squares.net/square-update-2.htm#Knecht
  4. 1 2 3 Harry White, http://budshaw.ca/Download.html
  5. Walter Trump http://www.trump.de/magic-squares/
  6. Johan Ofverstedt,http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-176018
  7. Harry White, http://budshaw.ca/Most-perfect.html
  8. 2x2 planar subsets,https://oeis.org/A270205
  9. Harvey Heinz,http://www.magic-squares.net/square-update.htm
  10. Chayes, J. T.; L. Chayes; C. M. Newman (1985). "The stochastic geometry of invasion percolation". Communications in Mathematical Physics. 101 (3): 383–407. Bibcode:1985CMaPh.101..383C. doi:10.1007/BF01216096.
  11. Damron, Michael; Artëm Sapozhnikov; Bálint Vágvölgyi (2009). "Relations between invasion percolation and critical percolation in two dimensions". Annals of Probability. 37 (6): 2297–2331. doi:10.1214/09-AOP462.
  12. van den Berg, Jacob; Antal Járai; Bálint Vágvölgyi (2007). "The size of a pond in 2D invasion percolation". Electron. Comm. In Probab. 12: 411–420. doi:10.1214/ECP.v12-1327.
  13. Tetzlaff, D.; McDonnell, J. J.; Uhlenbrook, S.; McGuire, K. J.; Bogaart, P. W.; Naef, F.; Baird, A. J.; Dunn, S. M.; Soulsby, C. (2011). "Conceptualizing catchment processes: simply too complex?". Hydrological Processes. 22 (11): 1099–1085. Bibcode:2008HyPr...22.1727T. doi:10.1002/hyp.7069.
  14. Fehr, E.; D. Kadau, N. A. M. Araújo, J. S. Andrade Jr., and H. J. Herrmann (2011). "Scaling Relations for Watersheds". Physical Review E. 84 (3): 036116. arXiv:1106.6200Freely accessible. Bibcode:2011PhRvE..84c6116F. doi:10.1103/PhysRevE.84.036116. Cite uses deprecated parameter |coauthors= (help)
  15. Schrenk, K. J.; N. A. M. Araújo, J. S. Andrade Jr., and H. J. Herrmann (2012). "Fracturing Ranked Surfaces". Scientific Reports. 2: 348. arXiv:1103.3256Freely accessible. Bibcode:2012NatSR...2E.348S. doi:10.1038/srep00348. Cite uses deprecated parameter |coauthors= (help)
  16. Fehr, E.; D. Kadau, J. S. Andrade Jr., and H. J. Herrmann (2011). "Impact of Perturbations on Watersheds". Physical Review Letters. 106 (4): 048501. arXiv:1101.5890Freely accessible. Bibcode:2011PhRvL.106d8501F. doi:10.1103/PhysRevLett.106.048501. Cite uses deprecated parameter |coauthors= (help)
  17. 1 2 3 Knecht, Craig; Walter Trump; Daniel ben-Avraham; Robert M. Ziff (2012). "Retention capacity of random surfaces". Physical Review Letters. 108 (4): 045703. arXiv:1110.6166Freely accessible. Bibcode:2012PhRvL.108d5703K. doi:10.1103/PhysRevLett.108.045703.
  18. Baek, Seung Ki; Beom Jun Kim (2012). "Critical Condition of the Water-Retention Model". Physical Review E. 85: 032103. arXiv:1111.0425Freely accessible. Bibcode:2012PhRvE..85c2103B. doi:10.1103/PhysRevE.85.032103.
  19. 1 2 Schrenk, K. J.; N. A. M Araújo; R. M. Ziff; H. J. Herrmann (2014). "Retention capacity of correlated surfaces". arXiv:1403.2082Freely accessible.
  20. Hoshen, Joseph (1998). "On the application of the enhanced Hoshen-Kopelman algorithm for image analysis". Pattern Recognition Letters. 19 (7). doi:10.1016/S0167-8655(98)00018-x.

Further reading

External links

This article is issued from Wikipedia - version of the 10/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.