April 2016 - mathfun@mailman.xmission.com

[math-fun] Ruperting the hypercube
by Warren D Smith 18 Apr '16

18 Apr '16

Take an N-dimensional cube. Rotate it randomly. The chance the original hypercube will be able to pass thru the result ("drilled hole" in "Prince Rupert's problem") by motion along the x-axis is (says Monte Carlo): N chance 2 99.999% 3 1.295% =approx= 1/77 =approx= exp(-4.35) 4 1 / (4*10^8) =approx= exp(-20) >=5 seems below 10^(-10) so empirically it looks as though the chance depends exponentially on a quadratic or cubic of N, for example chance =approx= N^(-((N-1)*N-2)) or something. That in turn would suggest that the maximum expansion factor indeed behaves like 1 + C^(-N) for some C>1, meaning the lower bound 1+const/9^N already has the right behavior (aside from changing the value of 9, and possible subexponential adjustments). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] points on NxN grid with no repeated distance (problem posed by Keith F. Lynch)
by Warren D Smith 18 Apr '16

18 Apr '16

Keith F. Lynch <kfl at KeithLynch.net> wrote: How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal? WDS: Let F(N) denote this quantity. UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N. STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214. LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works. CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

8 10

Re: [math-fun] "starshot"
by Henry Baker 17 Apr '16

17 Apr '16

Various forms of "spread spectrum" communications can overcome the relative power problem through "spreading codes". Briefly, spreading codes are a generalization of traditional sine & cosine encoding. By using more complex spreading codes, a receiver can accumulate a signal which is far below the "noise", but is still recognizable (and receivable) due to its spreading code. Thus, the receiver "tunes" to the appropriate "channel" by choosing the appropriate "spreading code". In a traditional/"narrow band" radio, this tuning is merely the choice of frequency -- i.e., the "spreading code" in this instance is a simple sine wave of the appropriate frequency. In a spread-spectrum radio, the local beat frequency oscillator (BFO) is replaced with a pseudo-noise PRNG (pseudo random number generator). It takes more work to establish synchronization than with a narrow band radio, but with the appropriate generalization, the overall block diagram of the radio is the same. https://en.wikipedia.org/wiki/Code_division_multiple_access At 05:02 PM 4/16/2016, rcs(a)xmission.com wrote: >One reason planets are hard to see is the nearby star swamping the signal. >If you choose a particular wavelength and signal encoding, you might get >something detectable against this background.

1 0

[math-fun] "starshot"
by Warren D Smith 17 Apr '16

17 Apr '16

"Russian venture capitalist Yuri Milner, along with physicist Stephen Hawking, has announced a $100 million initiative for exploring Alpha Centauri, the star system nearest to our own. The new project is called Breakthrough Starshot, and the goal is to explore the technologies needed to create small, light-powered spacecraft capable of reaching Alpha Centauri in just 20 years. The project will be led by Pete Worden, the former director of NASA's AMES Research Center. Facebook founder and CEO Mark Zuckerberg will join Hawking and Milner on the project's board of directors." --Might be nice if we can do some analysis on the back of an envelope showing that this entire fantasy is a total crock with zero hope. Allegedly the spacecraft would mass about 1 gram, consist of a small but amazing instruments and brain ("cameras, photon thrusters, power supply, navigation and communications equipment"), plus a light sail up to a few meters in diameter but only 3-1000 atoms thick. Accelerated by light pressure from huge lasers (located on the moon? some high altitude location on Earth?) to reach speed 0.2c. The lasers would be 1 km diameter. Supposedly that whole acceleration to 0.2c will take only a "few minutes." Flock of several thousand of them launched simultaneously by rocket, but only 1 is accelerated to relativistic speed at a time. How does it communicate back to us after reaches alpha centauri? Little or no idea. http://www.sci-news.com/space/breakthrough-starshot-plan-alpha-centauri-037… OK, here are a few calculations: Mass of sail 1000 angstrom thick, 10 meter^2 area, density of water: 1 gram. Kinetic energy of 1 gram at 0.2c: 1800 giga joules = 0.5 gigawatt hours. Can that much intelligence and sensory capability be done in 1gram? A large butterfly weighs a fraction of a gram and has eyes, navigation good enough to take it to one particular place in Mexico, brain, senses, thrust. So, maybe. Acceleration needed to reach 0.2c in 3 minutes: 34000 gees = 333000 meter/sec^2 which is about the same as a bullet experiences inside a pistol or rifle. For a 1 gram mass this is a force of 333 newtons. Tensile strengths: kevlar 3*10^8, steel 4*10^8, graphene 10^11 (all in pascals). So a 1000 angstrom thick film 1 meter wide with those strengths could pull 30-10000 newtons without breaking. Light pressure: A pressure of 100 newtons/meter^2 = 100 pascals on a reflective mirror, is achieved with beam power 30 gigawatt/meter^2. Lasers: wikipedia says "The AN/SEQ-3 Laser Weapon System or XN-1 LaWS is a directed-energy weapon developed by the United States Navy. The weapon was installed on USS Ponce for field testing in 2014... it generates (up to) 33 kWatt in testing..." a picture suggests the aperture diameter is about 2 feet, i.e. less than 1 meter. Allegedly the Navy claims it works well enough either as a weapon or in reverse as a telescope, that they want to keep it. So... looks like the laser beam intensity is a major problem for "starshot." Factor of a million short. I also have a hell of a big problem seeing how it could tell us anything from alpha centauri. There is some suspicion there are 1 or more planets orbiting one of the three alpha centauri stars, but so far that is unconfirmed. If we cannot even detect a freaking planet, then hard to detect communications from a tiny spaceprobe. If the power source was solar, then the probe will be within 1 AU of alpha centauri star for a total timespan of about 1.5 hours given its 0.2c speed. Even if it were capable of sending 1 bit per second (which seems to me incredibly optimistic) that'd be under 5 kbits total; I personally doubt (based on extrapolation of known bitrates from known spaceprobes), that it could send us even 1 bit ever. Actually perhaps the best try to send us 1 bit would be, if possible, to intentionally ram the spaceprobe into an asteroid so we could try to detect resulting explosion, which would be about 0.4 kilotons in nuclear weapons terminology. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 5

Re: [math-fun] "starshot"
by Warren D Smith 17 Apr '16

17 Apr '16

> Suppose they succeed in sending a micro craft to Alpha Centauri, > how would it communicate with us? > > Micro craft implies micro transmitter. How big a dish do you need to detect > a light bulb at a distance of 4 light years? --if a "light bulb" (100 watts worth of 500 nm wavelength photons, omindirectional) were to shine for 1 hour, that would be 9*10^23 photons emitted. At 4 light years away, that would yield a flux of 5*10^(-11) photons per square meter during that hour. So your "dish" would need to have radius=79.5 km to detect even a single one of those photons. However, by using a laser & telescope to shine the photons directly at our solar system, not omnidirectional, one could of course do considerably better. If your beam flared at angle 10^(-6) radians, then you'd increase the flux by a factor of 4*10^12, enabling a dish on earth to be able to receive 1 photon during that hour, with dish radius only 4 cm, i.e. an amateur telescope. Unfortunately, you'd also get a hell of a lot of other photons coming from alpha centauri's stars, which from Earth's point of view would still outshine that laser by a factor of about 10^12. If the laser instead of shining for 1 hour at 100 watts, instead somehow were to shine a 1 terawatt for 10^(-10) hours = 360 nanosec (same total energy), and the receivers knew at just what nanoseconds that was going to happen, then we could do better. Now, the stars only outshine the laser, from earth point of view, by factor 100. Therefore, with factor 100 outshining, earth observers could hope to detect the 1% brightness increase due to the laser, during those 360 nanosec, provided their "dish" had enough size to receive, say, 500 laser photons. So a mere 1 meter radius telescope on Earth, would suffice to receive 1 bit during that hour. And if we use the fact the laser were emitting 500 nm photons ONLY, while star emitting lots of colors, i.e. pipe our telescope thru a spectrograph into a photon detector, then we would do even better. Suppose the wavelength band is 500+-1 nm, receivers exclude all other wavelengths. Now, amazingly enough, that laser in earth's view actually is outshining the star by a factor of (very roughly) 10 during the right nanoseconds. So called "tabletop terawatt" chirped-pulse lasers can produce 1-picosec-long pulses with 1 terawatt power during that picosecond, at 10-Hz pulse rate, which is 10 watts. Therefore equipment available today hopefully fitting on 10 lab tables plus a telescope a few meters in diameter, plus some super-accurate atomic clocks, could transmit from alpha centauri to earth, perhaps a few 10s to 1000s of bits per hour with power supply of a few kilowatts to attain average transmission power 100 watts. This post here, is probably about 5 kilobits if compressed.

1 0

[math-fun] 3-coloring the rationals
by James Propp 17 Apr '16

17 Apr '16

There's a unique way to 3-color the rationals in [0,1] using the colors red, blue, and green so that 0 is red, 1 is blue, and the fractions a/b, c/d, and (a+c)/(b+d) all have distinct colors whenever ad-bc=1. Puzzle (no spoilers till Sunday please!): What color is 355/113? Jim Propp

3 5

Re: [math-fun] "starshot"
by Dave Dyer 17 Apr '16

17 Apr '16

>The proposed probes will be >power starved, but they can use a very narrow beam signal. A tiny craft can't make a focused radio signal. I suppose a laser com system would be possible, but even that would have a negligible energy density after 4 light years. My data point is that only the biggest dishes can communicate with voyagers now. Voyagers have orders of magnitude more power available, and are still orders of magnitude closer, than these probes will be.

1 0

Re: [math-fun] "starshot"
by Dave Dyer 16 Apr '16

16 Apr '16

Suppose they succeed in sending a micro craft to Alpha Centauri, how would it communicate with us? Micro craft implies micro transmitter. How big a dish do you need to detect a light bulb at a distance of 4 light years?

2 1

Re: [math-fun] "starshot"
by Dave Dyer 16 Apr '16

16 Apr '16

Suppose they succeed in sending a micro craft to Alpha Centauri, how would it communicate with us? Micro craft implies micro transmitter. How big a dish do you need to detect a light bulb at a distance of 4 light years?

1 0

[math-fun] polish expression for 'grosso modo' or the big picture
by Simon Plouffe 16 Apr '16

16 Apr '16

hello math-funers There is an expression in french for 'the big picture' which is 'grosso modo', which means ' approximately, this page explains the different ways to say the same in many languages here : http://www.expressio.fr/expressions/grosso-modo.php?utm_source=newsletter&u… and the funny thing is the polish expression, the big picture : Pi multiplied by a door , pi multiplié par une porte. I find this very funny! best regards, Simon Plouffe

3 3