July 2020 - mathfun@mailman.xmission.com

[math-fun] Torus question
by Dan Asimov 22 Jul '20

22 Jul '20

Here's a "puzzle" I don't know the answer to offhand: Call two points X, Y' of the plane "equivalent": X ~ X' if they differ by an integer point: X' = X + v for some v in Z^2. Likewise, call any two circles C, C' in the plane "equivalent": C' ~ C if one is a translation of the other by an integer translation: C' = C + w for some w in Z^2. Now let A, B, C be any three distinct points in R^2. Among all possibilities for A, B, C, what is the maximum number of inequivalent circles that pass through 3 points A', B', C' with A' ~ A, B' ~ B, C' ~ C such that no points equivalent to A, B, or C lie in the interior of such a circle ??? —Dan --------- What is the maximum number of circles Unrolling the torus to obtain the plane results in all the points of the form A + (K,L), B + (K,L), C + (K,L) appearing on the plane

1 0

[math-fun] Last 4 digits of S sum up to a square
by Éric Angelini 18 Jul '20

18 Jul '20

Hello Math-fun, S = 1, 2, 4, 9,... If we want S to be the lexicographically earliest seq of distinct positive terms, we cannot have another start (like 1, 2, 3, X). The seq is finite — but how many terms can we plug in? I think we could extend S with 12: S = 1, 2, 4, 9, 12,... (the last 4 digits have sum 16 again — a square). Instead of 12 we could have extended S with 21, 30 or 999. This idea opens the way to a few variants, of course (sum k digits instead of 4, get a prime instead of a square), etc. Best, É. Catapulté de mon aPhone

2 3

[math-fun] Rectilinear crossing numbers (was Re: Number of ways to pick 4 points from an m X n grid?)
by Keith F. Lynch 18 Jul '20

18 Jul '20

The term "rectilinear crossing number" (RCN) for Kn (the complete graph on n points) seems to be used interchangeably for the smallest such number and for every such number. Is there an official way to distinguish? I hope it's clear from context in the following which I mean in each case. Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: > .... So your numbers are right. Thanks. I always like to hear that. :-) > "Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: >> So with six points I expected to get four possible numbers of >> crossings. Instead, I got eleven, from 3 to 15. I don't know >> what most of them mean. >> I looked up 1,2,3,11 in OEIS, and I get way too many hits. >> I guess I'll have to try 7 points, to get the next term. I tried 7 through 30 vertices. The series seems to start 1,1,1,2,3,11,13,47,52,136. But the last three terms are almost certainly wrong. The 11 (for K6) is probably right, since I get at least a six-digit number of hits for every RCN that gets any hits at all (3,4,5,6,7,8,9,10,11,12,15). The 13 (for K7) is probably right, since I get at least a five-digit number of hits for every RCN. The 47 (for K8) is probably wrong, since one of them (64) gets only one hit. Other than that, they all get at least a four-digit number of hits, and 15 of them get more than a million hits each. Given how irregular that one is, I'm no longer certain of the 13, or even the 11. With that caveat, the series doesn't seem to be in OEIS. The 136 (for K10) is certainly wrong, since the smallest RCN I found was 63, but A014540 says the (minimal) RCN for K10 is 62. The smallest RCNs I get for K11 through K30 also exceed the official numbers. And the *largest* RCNs I get for K13 through K30 are all too low, meaning that the odds of more than a dozen randomly placed points all being on their convex hull are very slim. OEIS says the RCN for K28 is definitely either 7233 or 7234. I get 8995, which gets just one hit. That's with 2.5 million random sets of 28 points. Sigh. > The maximum number of intersections is always (n choose 4). > If you pick any four of the vertices, there's just one interior > intersection formed by edges between them. Thanks. > The number of _distinct points_ they produce can be less when more > than two edges meet at a point. As a computer guy, I've always been comfortable with the idea that two points can be in the same place. Apparently mainstream mathematicians don't think that way. > I don't have much intuition for which of the numbers in [rectilinear > crossing number, (n choose 4)] are actually attainable. Unless the > pattern is very simple, I suspect it's going to be pretty tough to > count them. Indeed. Scattering points at random, as I've been doing, can at best give a lower limit to how many such numbers there are for Kn. And at best can give an upper limit to the minimal RCN for each Kn. What's needed is a way to look at every possible arrangement of n points. By "arrangement" I don't mean the uncountable infinity of possible locations of points in the unit square, I mean a difference that makes a difference. After some thought, I'm convinced that a crossing number for a specific arrangement of n points can only change if one of the points crosses an edge. So for any n there are certainly only a finite number of arrangements. There are n-choose-3 triangles and for each triangle each vertex is either in it or not in it. (A vertex can be in multiple triangles, since many triangles overlap.) (I don't count the vertices *of* a triangle as being in that triangle.) So the maximum number of arrangements is 2^n * n-choose-3. It will usually be much less, since most such arrangements are impossible. (Alternatively, for each pair of edges that don't share an endpoint, they either cross or not, so that's 2^(3*(n-choose-4)), but I think that's usually a much larger number.) How would one go about enumerating all arrangements? Starting from a regular n-gon, you could do a depth-first or breadth-first search in which vertices cross accessible edges, where "accessible" means the vertex can cross it without crossing another edge first and without dragging one of its own edges across another vertex. You'd be done when every possible move reaches an arrangement that's already been found. Getting back to n=6, I still have no idea, for most of the 11 RCNs, which of them correspond to each of the four possible perimeters (triangle containing three points, ..., convex hexagon containing no points), or whether one of them can correspond to two possible perimeters. I had previously guessed that the number of RCNs was equal to the number of possible perimeters, at least through n=6. For n=7, I thought I might get an additional RCN that distinguishes between a triangle containing a convex quadrilateral and a triangle containing a triangle containing a point, for a total of 6 RCNs. Instead I get 13. Who knew that points in a plane and the lines connecting them could be so complicated? Does anyone know of any good online sources that explain what's known? I looked up the RCN Project, but there's little useful information there, and its website doesn't seem to have been maintained or updated since about a decade ago anyhow. One thing I have noticed is that the next to largest RCN for Kn always seems to be n-3 less than the largest RCN for Kn. That makes sense, since pushing one of the vertices just enough that the figure is no longer convex means the edge connecting its neighboring vertices to each other no longer crosses anything, when previously it had crossed all but 2 of the N-1 edges that terminate on the vertex we moved.

2 1

Re: [math-fun] Number of ways to pick 4 points from an m X n grid?
by Keith F. Lynch 17 Jul '20

17 Jul '20

Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: > "Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: >> With 216 billion sets, I get 0.356188363, even closer to that >> formula. That's the probability of a convex pentagon given five >> random points in a circle. The probability of a quadrilateral with >> one point in it is 0.548822606, and the probability of a triangle >> with two points in it is 0.094989031. > Suppose we pick five points in some region R (say, a circle). > They form a convex pentagon _unless_ one of them lies within > the triangle formed by three others. The expected number of > times this happens is (5 choose 2) times the probability that > a given point lies within a given triangle, which is 10 times > the expected (area of triangle / area of R) so, calling that > ratio f, the expected number of counterexamples to convexity > is 10f. > .... So, finally, we need 1 - 10.35/48pi^2 + 10.3/32pi^2 > which equals 1 - 1/48pi^2 (350 - 45) = 1 - 305/48pi^2 > matching the value you found. (Phew.) Thanks! What are the odds of a convex quadrilateral with one point in it, and the probability of a triangle with two points in it? They look like they might be 260/48pi^2 and 45/48pi^2 respectively (aka 65/12pi^2 and 15/16pi^2 respectively). > One could in principle do the same sort of calculations for any > number of points, but they get messier. Also, the fact that we > ended up with two (rational/pi^2) terms is kinda-coincidental; with > six points we would need the expected _cube_ of (area(T)/area(R)), > and if my calculations -- more honestly, my invocations of > Mathematica's symbolic integration facilities -- are right > then the expectation of area(T)^3 is 1001/(3200pi) Interesting. It's a good thing I guessed right as to the form, given that Plouffe's Inverter and the Inverse Symbolic Calculator are down. Does anyone know of another website which, given a few digits of a real number, gives what the number might be? > and so we will start to get terms with pi^4 in the denominator as > well as ones with pi^2 in the denominator. (Which will also make it > trickier to guess the right answer purely by numerical experiment...) Especially since the calculations get slower as the number of points go up. I've started working on six points. With three points, I get no crossings (of line segments joining the points), with four points I get either zero, representing a triangle with a point in it, or one, representing a quadrilateral, and with five points I get either 1, 3, or 5 crossings, representing a triangle containing 2 points, a convex quadrilateral containing 1 point, or a convex pentagon, respectively. So with six points I expected to get four possible numbers of crossings. Instead, I got eleven, from 3 to 15. I don't know what most of them mean. I looked up 1,2,3,11 in OEIS, and I get way too many hits. I guess I'll have to try 7 points, to get the next term. It could be a bug in my program, but I don't think so. I've confirmed that 3 is indeed the smallest number of crossings for K6. It's the "rectilinear crossing number," A014540. I'm surprised that there's no known formula for it, and that the solution for graphs as small as K28 are unknown. And I've confirmed that 15 is indeed the largest number of crossings for K6. I'm still trying to figure out the formula for that, given that I was mistaken when I assumed that, given a convex N-gon, every edge other than those on the perimeter, or those that share a vertex, crosses every other such edge. For the regular hexagon, some edges are parallel, and there are 15 crossings. I don't think the number can differ from 15 for an irregular (but still convex) hexagon, since (unless I'm confused) gradually transforming a regular hexagon into that irregular hexagon can't change the crossing number unless an edge passes through a vertex during the transformation, and there are no vertices in the interior for any edge to pass through. Perhaps I should attempt to find the rectilinear crossing number for K28 with my program. There will always be 3(n choose 4) pairs of edges to check for intersections. For n=28 that's 61425 pairs, which is not completely intractable.

2 1

[math-fun] pandemic 'pooled'/sewage testing
by Henry Baker 17 Jul '20

17 Jul '20

I was listening to the latest "TWiV" (This Week in Virology) podcast, where Dr Michael Mina, Asst. Prof. Epidemiology at Harvard, was being interviewed. Mina is incredibly sane, and he provided some interesting insights about 'pooled' testing. Let's say that a standard test can easily detect the virus when there's 10^5 - 10^6 virus particles. But someone who is shedding, is probably shedding perhaps 10^12 virus particles. So, even if only 1 person in a *million* is shedding virus particles, it would be picked up with a single sewage test (assuming good mixing). On the other hand, if the virus is *already* present in the community, then sewage testing won't help, because the needle will be pinned at 100% all the time. So the best time for sewage testing is *before* the virus becomes well spread, and is therefore perfect for monitoring 'naive' (non-exposed) populations prior to their becoming infected. Furthermore, the doubling time of virus particles *within a single human* is on the order of minutes or tens of minutes, so if the test is wrongly negative one day, it will almost certainly be picked up the next day when the # of particles will have grown by several orders of magnitude. So sewage testing also has the ability to test almost *continuously*, so that warning bells can go off ASAP. Mina also pointed out the advantages of *quick feedback*. The current testing results latency in some communities -- e.g., San Diego -- is running 10 days. This makes the tests -- no matter how precise -- essentially useless for any kind of quarantining or contact tracing. A cheap, quick test -- e.g., spit on a little stick and look for a color change -- could change things dramatically, even if the test weren't particularly sensitive or precise. This is because a person could be testing 1x/day -- e.g., when coming to work -- or even more often -- prior to seeing a patient. As Dr. Mina pointed out, even if someone is incubating the virus, and one test misses it, the chance that the next test would miss a 100x signal (due to replication in the interim) is extremely small. It's nice to know that there are some excellent people out there working on this problem.

1 0

[math-fun] Stereography cures eccentricity!
by Bill Gosper 16 Jul '20

16 Jul '20

https://en.wikipedia.org/wiki/Stereographic_projection#/media/File:LRO_WAC_… —rwg

2 1

[math-fun] Prob. that 2 numbers relatively prime, error term?
by Neil Sloane 15 Jul '20

15 Jul '20

A018805(n) is no. of pairs (x,y) in [1..n]X[1..n] with gcd(x,y)=1. It is ~ 6*n^2/Pi^2 + C*n*log n, I think. What is C, and how can one find it using Mathematica or some other program? I ask because there are several similar sums I am interested in. Is there a reference? Background: A331755 has an explicit formula (involving A018805) and is ~ 9*n^4/(8*Pi^2) + O(n^3 log n). A331763 is a mystery that I would love to solve, and seems to be ~ constant*n^4/Pi^2. Maybe knowing the second terms in the asymptotic expansions would help with the curve-fitting.

4 5

Re: [math-fun] real numbers and the laws of physics
by Dan Asimov 15 Jul '20

15 Jul '20

Sorry, I find this to be utter, complete, total hogwash. —Dan ----- Any volume of space is known to have a finite information capacity (with the densest possible information storage happening inside black holes). The universe’s initial conditions would, Gisin realized, require far too much information crammed into too little space. “A real number with infinite digits can’t be physically relevant,” he said. The block universe, which implicitly assumes the existence of infinite information, must fall apart. -----

1 0

[math-fun] How does a dull spoon manage to cut a stringy piece of meat
by Bill Gosper 14 Jul '20

14 Jul '20

while sliding back an forth against the inside of a slippery bowl? --rwg

5 9

Re: [math-fun] Counting vs. cross-products vs. tree traversal
by Steve Witham 13 Jul '20

13 Jul '20

> From: Andy Latto <andy.latto(a)pobox.com> > Date: 7/11/20, 1:24 AM > > On Mon, Jun 29, 2020 at 6:01 PM Steve Witham <sw(a)tiac.net> wrote: >> ...In contrast I find tree-traversals (usually implicit) one of the most >> awkward tasks in programming. > This maybe belongs on programming-fun rather than math-fun, but I > don't see the awkwardness at all. The reason I posted here was the kids-can-count-in-decimal angle. > ;;; GIven a function that, when called on a node of a tree, returns > the list of child nodes, apply a given processing function to all > nodes > ;;; of the tree in depth-first order. > > (defun depth-first-process (root-node children-function processing-function) >Â Â Â Â (map #'(lambda (child) (depth-first-process child > children-function processing-function)) >Â Â Â Â Â Â Â Â Â Â Â Â Â (funcall children-function root-node)) >Â Â Â Â (funcall processing-function root-node)) Touche... def depth_first(root, children_of, process): Â Â Â """ Â Â Â Given root-- a node, Â Â Â Â Â Â Â children_of-- a generator that yields the sub-nodes of a node, Â Â Â Â Â Â Â process-- a function to apply to every node, Â Â Â Call process on every node, bottom-up, and return the last result. Â Â Â """ Â Â for child in children_of(node): Â Â Â Â Â depth_first(child, children_of, process) Â Â Â return process(root) The case I was working on was like Â Â Â for a in pick_As(): Â Â Â Â Â Â for b in pick_Bs(a): Â Â Â Â Â Â Â Â Â Â for c in pick_Cs(a, b): Â Â Â Â Â Â Â Â Â Â Â Â Â Â for d in pick_Ds(a, b, c): Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â for e in pick_Es(a, b, c, d): Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â run_the_test(a, b, c, d, e) or is it def pick_As(): for a in ...: pick_Bs(a) def pick_Bs(a): for b in ...: if constraintB(a, b): pick_Cs(a, b) def pick_Cs(a, b): for c in ...: if constraintC(a, b, c): pick_Ds(a, b, c) ... The digit-counter idea did get me through reasonably neatly. > Where is the awkwardness and the bookkeeping in this two-line function? Well it doesn't start in your function, but as sensible-seeming constraints in a problem.Â The awkwardness is when I find myself clumsily hogtied by perfectly good christmas light strings 3/4 of the way down a perfectly good tree. The digit counter idea gave me a static structure I could fit the constraints onto, with a main loop to zip up and down them. Â --Steve

1 0