A Purely Geometric Variant of the Gale–Berlekamp Switching Game
Adrian Dumitrescu, Jeck Lim, János Pach, Ji Zeng · 2025
Read A Purely Geometric Variant of the Gale–Berlekamp Switching Game by Adrian Dumitrescu, Jeck Lim, János Pach, Ji Zeng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16305.txt.
Introduction
Dumitrescu and co-authors set a shape form of a known switch game. The base game flips signs on a board to lift the sum. Their form uses points in a plane, each marked plus or minus one. No three points in the set share one line in the set-up. A move picks a line through at least two of the points. That move flips the sign of each point on the line.
The aim is to push the whole sum as high as it can go. The team shows a score of n less a small share is safe. For each n, a score of at least n per three is safe too. Both bounds come with a fast step plan to reach them. The plan runs in matched time by their proof.
Catalog record
| CREATOR | Adrian Dumitrescu, Jeck Lim, János Pach, Ji Zeng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-16305
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Purely Geometric Variant of the Gale–Berlekamp Switching Game Adrian Dumitrescu, Jeck Lim, János Pach, Ji Zeng Abstract We introduce the following variant of the Gale–Berlekamp switching game. Let P P be a set of n noncollinear points in the plane, each of them having weight + 1 +1 or − 1 -1 . At each step, we pick a line ℓ \ell passing through at least two points of P P , and switch the sign of every point p ∈ P ∩ ℓ p\in P\cap\ell . The objective is to maximize the total weight of the elements of P P . We show that one can always achieve that this quantity is at least n − o ( n ) n-o(n) , as n → ∞ n\rightarrow\infty , and at least n / 3 n/3 , for every n n . Moreover, these can be attained by a polynomial time algorithm. Algoresearch L.L.C., Milwaukee, WI, USA [email protected] 0000-0002-1118-0321 California Institute of Technology, Pasadena, CA, USA [email protected] Alfréd Rényi Institute of Mathematics, Budapest, Hungary [email protected] 0000-0002-2389-2035 Alfréd Rényi Institute of Mathematics, Budapest, Hungary [email protected] ccs Mathematics of computing Discrete mathematics ccs Theory of Computation Randomness, geometry and discrete structures keywords maximum discrepancy, switching game, ordinary line † † runningtitle: A Purely Geometric Variant of the Gale–Berlekamp Switching Game † † runningauthor: Adrian Dumitrescu, Jeck Lim, János Pach, and Ji Zeng † † copyright: Adrian Dumitrescu, Jeck Lim, János Pach, and Ji Zeng † † funding: Work on this paper was supported by ERC Advanced Grant no. 882971 “GeoScape”. Work by the second named author was partially supported by an NUS Overseas Graduate Scholarship while in residence at the Simons–Laufer Mathematical Sciences Institute during the Spring 2025 semester. Work by the third named author was also supported by the Eisenbud Professorship and and by a Clay Senior Scholar fellowship at the IAS/Park City Mathematics Institute in July 2025. Work by the fourth named author was also supported by ERC Advanced Grant no. 101054936 “ERMiD”, and by NSF grant DMS-1928930 while in residence at the Simons–Laufer Mathematical Sciences Institute during the Spring 2025 semester. 1 Introduction The Gale–Berlekamp switching game (introduced in the 1960 s) can be described as follows. Consider a \sqrt{n}\times\sqrt{n} array of n lights. Each light has two possible states, on (or +1 ) and off ( -1 , respectively). To each row and to each column of the array there is a switch. Turning a switch changes the state of each light in that row or column. Given an initial state of the board, i.e., a certain on or off position for each light in the array, the goal is to turn on as many lights as possible. Equivalently, the number of lights that are on minus the number of lights that are off should be as large as possible, when starting from the initial configuration. See Fig 1 . The first correct analysis of the original version of the game with n=100 was given by Carlson and Stolarski [ 10 ] in 2004. (cf. [ 15 ] .) Figure 1: A 5\times 5 grid for the original game whose signed discrepancy is 5 and whose maximum signed discrepancy is 15 (left); points with weight -1 are red. The latter parameter becomes 25 in the purely geometric variant, where one switches all lights along any line (not necessarily vertical or horizontal) spanned by the points. By a configuration we shall mean the state of the machine, i.e., precisely which lights are on and off. Following Beck and Spencer [ 4 ] , define the signed discrepancy of a configuration as the number of lights that are on minus the number of lights that are off. Equivalently, this is just the sum of the weights +1 and -1 corresponding to the on and off lights, respectively. The asymptotic behavior of the original version of the game, played on the \sqrt{n}\times\sqrt{n} square board, was studied by Brown and Spencer [ 8 ] and revisited by Spencer [ 26 ] . They showed that one can always achieve a signed discrepancy of \Omega(n^{3/4}) and that the order of magnitude of this bound cannot be improved. Interestingly enough, both the upper and the lower bound are obtained by the probabilistic method [ 1 ] . Here we consider the following, purely geometric, variant of the switching game. The board is any noncollinear n -element point set P in the plane, equipped with a switch for each connecting line. A configuration is a pair (P,w) , where w is an assignment of \pm 1 weights to the elements of P . Denote by |w| the sum of the weights \sum_{p\in P}w(p) . Let F(P,w_{0}) denote the largest signed discrepancy that can be achieved by applying a series of switches to the initial configuration (P,w_{0}) , that is, let F(P,w_{0})=\max_{w}|w|, (1) where the maximum is taken over all weight assignments w:P\rightarrow\{+1,-1\} that can be obtained starting with the initial assignment w_{0} . Finally, define F(P)=\min_{w_{0}}F(P,w_{0}), (2) where w_{0} runs through all initial weight assignments. We show that, regardless of the initial assignment, if n is large enough, then a skilled player can always achieve a linear signed discrepancy cn , for any constant c arbitrarily close to 1 and independent of P . Further, one could do this by only applying a linear number of switches out of possibly a quadratic number. Theorem 1 . For any noncollinear n -element point set P in the plane, consider a board where there is a switch for each connecting line. Then we have F(P)\geq n-o(n) , i.e., in the corresponding game, one can always turn on at least n-o(n) lights. Moreover, the lower bound can be achieved by an application of O(n) switches. Our next theorem below gives a concrete bound that holds for every n . Theorem 2 . For any noncollinear n -element point set P in the plane, consider a board where there is a switch for each connecting line. Then we have F(P)\geq n/3 , i.e., in the corresponding game, one can always turn on at least 2n/3-1 lights. Moreover, the lower bound can be achieved by an application of O(n) switches. Notice that if n is odd and all but one of the points of P are collinear, then we have F(P)\leq n-2 . Indeed, if initially an odd number of lights are off (-1) , then one cannot turn all lights on, because no switch can change the parity of the off lights. Actually, it is easy to see that for this board, we have F(P)=n-2 . On the other hand, if n is even and all but one of the points of P are collinear, then one can turn on all the lights. See Fig. 2 . Figure 2: Two warm-up board examples. Our proofs crucially rely on the concept of ordinary line . Given a point set P , a connecting line is called ordinary if it contains precisely two points of P [ 5 ] . It will be evident from the proof of Theorem 2 that repeatedly computing a line incident to the maximum number of points and reducing the current size by 3