May 2018 - mathfun@mailman.xmission.com

[math-fun] "I don't find this proof beautiful" quote?
by James Propp 29 May '18

29 May '18

Some fancy-pants literary intellectual like Louis Menand or Anatole Broyard once unabashedly professed a failure to see the beauty in the proof of the infinitude of the primes (or maybe it was the proof of the irrationality of the square root of two). Does anyone know the quote I'm thinking of? I apologize if I've asked this before, especially if it was in the past five years. (Is there a single document somewhere out there that has absolutely everything that's ever been posted to math-fun?) Thanks, Jim Propp

4 6

[math-fun] Area[sQUIRKle]
by Bill Gosper 28 May '18

28 May '18

Instead of just getting 4/Binomial[2/p,1/p] (or equivalent but messy 𝝘 functions) from Assuming[p > 0, 2 Integrate[(1 - Abs[x^p])^(1/p), {x, -1, 1}]], Assuming[p > 0, Area[ImplicitRegion[Abs[x^p] + Abs[y^p] < 1, {x, y}]]] does weird things that don't always work: 1/3 Area[ImplicitRegion[Abs[x]^(1/3)+Abs[y]^(1/3)<1,{x,y}]] 1/2 2/3 2/3 Area[ImplicitRegion[Abs[x]^(2/3)+Abs[y]^(2/3)<1,{x,y}]] 1 2 3/2 (2 2^(2/3) √π Gamma[2/3])/Gamma[1/6]-(2^(2/3) √(3 π) Gamma[5/6])/Gamma[-(2/3)] 2 π 5/2 - 5 √(2/(5+√5)) π Gamma[7/5])/(Gamma[-2/5] Gamma[4/5]))+(2^(1/5) √π Gamma[7/5])/Gamma[9/10] 3 3 3^(1/3) AppellF1[4/3,-(1/3),-(1/3),7/3,-(1/(-1+(-1)^(2/3))),1/(1+(- 1)^(1/3))] 2 √3 (2^(1-1/Sqrt[3]) Sqrt[\[Pi]/3] Gamma[1/(2 Sqrt[3])])/Gamma[1/6 (3+Sqrt[3])] 4 (8 Gamma[5/4]^2)/√π 9/2 (2^(5/9) √π Gamma[11/9])/Gamma[13/18]+(π Csc[2 π/9] Gamma[11/9])/(Gamma[4/9] Gamma[7/9]) 5 (2 2^(3/5) √π Gamma[6/5])/Gamma[7/10] Notice the AppellF1 for p=3, which must equal 4/Binomial[2/3,1/3], unbeknownst to FullSimplify. Is it beknownst to anybody? --rwg

1 1

[math-fun] Gamma and qin(x)
by françois mendzina essomba2 27 May '18

27 May '18

I keep in memory (qos(x))^4+(qin(x))^4=1 and : qin(sigma/2)=1, qin(sigma/4)=2^(-1/4) . I looked for the equivalent of the formula Gamma(1-z)*Gamma(z)=Pi/(sin(z*Pi)) with the function qin(x). I imagined that the following equalities are correct, I could verify numerically. integrate((1-x^4)^(-3/4), x, 0, 1)=(sigma/2)/qin(sigma/2); integrate(x^4*(1-x^8)^(-7/8), x, 0, 1)=(sigma/4)/qin(sigma/4); but I was wrong about this equality, it is not correct. integrate(x^12*(1-x^16)^(-15/16), x, 0, 1) = (sigma/8)/qin(sigma/8); Why ??? The first answer may be related to the nature of the squircle itself, on an axis, its area can not be divided into several equal parts. We can only get 2 or 4 equal parts. but I remain convinced that there must be this type of formula

2 2

Re: [math-fun] math-fun Digest, Vol 183, Issue 43
by françois mendzina essomba2 27 May '18

27 May '18

Area[sQUIRKle] Hello, I like the subject that concerns the area of the circle and squirkle but this result is unknown to me Le dimanche 27 mai 2018 à 19:00:16 UTC+1, <math-fun-request(a)mailman.xmission.com> a écrit : Send math-fun mailing list submissions to math-fun(a)mailman.xmission.com To subscribe or unsubscribe via the World Wide Web, visit https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun or, via email, send a message with subject or body 'help' to math-fun-request(a)mailman.xmission.com You can reach the person managing the list at math-fun-owner(a)mailman.xmission.com When replying, please edit your Subject line so it is more specific than "Re: Contents of math-fun digest..." Today's Topics: 1. Area[sQUIRKle] (Bill Gosper) ---------------------------------------------------------------------- Message: 1 Date: Sat, 26 May 2018 15:59:31 -0700 From: Bill Gosper <billgosper(a)gmail.com> To: math-fun(a)mailman.xmission.com Subject: [math-fun] Area[sQUIRKle] Message-ID: <CAA-4O0EbSsA+P3E3xuD30FJsRagn+qyHRYa13t5FKu2X+VmGrw(a)mail.gmail.com> Content-Type: text/plain; charset="UTF-8" Instead of just getting 4/Binomial[2/p,1/p] (or equivalent but messy ? functions) from Assuming[p > 0, 2 Integrate[(1 - Abs[x^p])^(1/p), {x, -1, 1}]], Assuming[p > 0, Area[ImplicitRegion[Abs[x^p] + Abs[y^p] < 1, {x, y}]]] does weird things that don't always work: 1/3 Area[ImplicitRegion[Abs[x]^(1/3)+Abs[y]^(1/3)<1,{x,y}]] 1/2 2/3 2/3 Area[ImplicitRegion[Abs[x]^(2/3)+Abs[y]^(2/3)<1,{x,y}]] 1 2 3/2 (2 2^(2/3) ?? Gamma[2/3])/Gamma[1/6]-(2^(2/3) ?(3 ?) Gamma[5/6])/Gamma[-(2/3)] 2 ? 5/2 - 5 ?(2/(5+?5)) ? Gamma[7/5])/(Gamma[-2/5] Gamma[4/5]))+(2^(1/5) ?? Gamma[7/5])/Gamma[9/10] 3 3 3^(1/3) AppellF1[4/3,-(1/3),-(1/3),7/3,-(1/(-1+(-1)^(2/3))),1/(1+(- 1)^(1/3))] 2 ?3 (2^(1-1/Sqrt[3]) Sqrt[\[Pi]/3] Gamma[1/(2 Sqrt[3])])/Gamma[1/6 (3+Sqrt[3])] 4 (8 Gamma[5/4]^2)/?? 9/2 (2^(5/9) ?? Gamma[11/9])/Gamma[13/18]+(? Csc[2 ?/9] Gamma[11/9])/(Gamma[4/9] Gamma[7/9]) 5 (2 2^(3/5) ?? Gamma[6/5])/Gamma[7/10] Notice the AppellF1 for p=3, which must equal 4/Binomial[2/3,1/3], unbeknownst to FullSimplify. Is it beknownst to anybody? --rwg ------------------------------ Subject: Digest Footer _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ------------------------------ End of math-fun Digest, Vol 183, Issue 43 *****************************************

1 0

[math-fun] power side-channel resistant logic impossible?
by Henry Baker 24 May '18

24 May '18

I've been pondering the problem of building logic gates whose power consumption is *100% independent* ("power oblivious"?) of the input & output values. I'm starting to think that this task may be impossible. Here are my reasons: 1. Digital logic depends upon the ability to *standardize* signals to 0's and 1's with a significant *margin* between a 0 or a 1. Thus, each logic gate has a definition of what inputs it is willing to *accept*, and what outputs it is capable of *producing*. So long as the "producing" signals are a subset of the "accepting" signals, then the logic family will operate correctly as logic gates. However, operating correctly as logic gates won't necessarily eliminate the *power side-channel* which can leak information about what values are being operated on and what values are being produced. There are several sources of *noise* and *variability* of these signals. Noise is uncertainty produced by inherent statistical variation -- e.g., the number of electrons being switched -- or *interference* ("crosstalk") from other signals -- or faint traces of *history* from previous gate computations. Variability comes from manufacturing differences -- e.g., variations in the sizes of gates, lengths of wires, etc. One of the major successes of digital circuitry is its resistance to both kinds of variation -- noise and manufacturing variability. However, in the case of power side-channels the variation is no longer *statistical* because we're dealing with an individual circuit and an individual gate. Given enough measurements, we can likely characterize *each and every separate gate* on a chip and identify its unique characteristics. 2. Another kind of noise has to do with the *history* of a particular signal -- e.g., which paths the signal has taken to get to a particular gate. Yes, the signal falls within the limits of acceptability to the gate, but minor differences in the signal can still "leak through" the gate and end up as minor differences in the output of the gate. Thus, although the zero-th order of the signal is a "0" or "1", the remaining orders of the signal may incorporate information about the history of the signal which may be leaked through the power consumption of the subsequent gates. Yes, we could significantly *tighten* the *standardization* for each signal, and therefore narrow the *acceptability* of each gate, but this would dramatically reduce the performance and increase the cost of the resulting system circuits. After all, one of the major reasons for preferring digital circuits over analog circuits in the first place is to avoid the tight manufacturing constraints of high precision analog circuits. 3. One of the means to reduce the power side-channel is to *mirror* certain computations in an effort to compensate for a variation in one version of the computation with an offsetting variation in the other version of the computation. The simplest version of this is "differential signaling", where only the *difference* between two signals is significant, and the *common mode* -- the signal appearing on both mirrored outputs -- is ignored. Unfortunately, while the common mode for signals can be rejected for computation purposes, *power -- being a quadratic function -- cannot be rejected*, since all contributions are positive. Since there is no such thing as "negative power", there is no way to "subtract" this common mode power. 4. Timing. One possibility to avoid manufacturing variation issues is to utilize *the same* circuitry to perform the *mirror image* calculation. Thus, one might perform two (or more) calculations with different inputs and outputs on *the same gates* to confuse any power watchers as to exactly which computation is the *real* computation. While these computations still can't mirror all of the noise issues, they can -- in theory -- remove actual gate size and actual wire length from contributing to the side-channel. However, it appears to be quite difficult to hide *which calculation is the real one*, and since they are separated in time, it is still possible to measure them all through the power side-channel. 5. Quantums ? Perhaps the only solution will be a simplified version of "quantum computation" in which a signal is a *single electron* or a *single photon* -- i.e., a single quantum -- so that the *standardization* of the signal is due to the *identical* behavior of each quantum (electron or photon). As in (QKD) quantum key distribution, the problem is now making sure that only one quantum appears on a wire at any one time; two or more quanta produce an error that needs to be corrected. Unfortunately, such a simplified quantum computer may not be so easy to build, as it requires *eliminating* all other quantum behavior -- e.g., *superposition* and *entanglement* -- which behavior is actually *desired* by the builders of so-called "quantum computers". So in the end, eliminating these *quantum side channels* also means eliminating most *quantum behavior*. --- I don't have any answers, but I'm wondering if eliminating the power side-channel may simply be impossible from a theoretical point of view. An analogy might be eliminating *glitches* from *arbiters*, and there may even be a connection between these two problems.

2 1

[math-fun] Colliding bullets problem
by David Wilson 24 May '18

24 May '18

I originally posted the "colliding bullets problem" to math-fun, which was later posted to https://www.research.ibm.com/haifa/ponderthis/challenges/May2014.html and apparently it is starting to motivate some research: https://arxiv.org/abs/1610.00282 https://arxiv.org/abs/1709.00789

1 0

Re: [math-fun] number arithmetic: power side-channels?
by Henry Baker 21 May '18

21 May '18

You are correct. After additional Googling, I found SABL ("Sense Amplifier Based Logic"), by UCLA's Tiri, et al., (2002). In additional to constant static power consumption, SABL provides "equal" dynamic power consumption, regardless of bit patterns. "Equal" here doesn't mean constant, hence it is better than ECL; however, there is a mean "constant- sized" current spike every clock cycle where essentially every gate+wire changes state. SABL costs ~2x in size (wires, gates), perhaps ~2X in speed, and at least ~4x in power consumption over "standard" CMOS. I'm coming around to a "new" (?) idea: in addition to an extensive on-chip clock distribution network, future secure chips may require an equally extensive on-chip *randomness distribution network* to guarantee a source of randomness for every gate and every wire. Such a distribution network may require 1-2 additional wiring layers, but I doubt it will double the number of layers. Simply randomizing the clock itself doesn't do much good if someone can access the clock to trigger logging. (Most digital systems already use some form of "spread spectrum" PRNG clocking in order not to cause RFI and run afoul of the FCC.) Asynchronous systems may not have synchronized clocks, but they do tend to do roughly the same thing when faced with the same computation, so merely asynchronizing circuitry won't help a lot unless one also actively adds additional randomness in some way. Also, asynchronous circuits try to always run at top speed, which maximizes dynamic power consumption and electromagnetic emissions, so free-running asynchronous logic is probably not what is wanted for these applications. At 08:15 PM 5/19/2018, Tomas Rokicki wrote: >Just having inverse signals doesn't solve the problem. >CMOS power consumption is primarily *switching* from >0 to 1 or 1 to 0 (except for leakage of course). > >So to make this truly work you'd need to somehow >have logic that for every 0-1 transition on one gate, >there's a lack of transition on a nearby gate. > >-tom > >On Sat, May 19, 2018 at 5:59 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> First step, combinational logic: >> >> "Differential signaling": for every signal wire A, there's an >> equal and opposite signal wire (not A). >> >> For every gate, there's a paired dual gate: AND <-> OR; >> NOT <-> NOT. >> >> Blows up every wire to double wires, blows up every gate >> to double gates. >> >> In a perfect (quasi static) world, the total power would >> remain the same regardless of the parity of any of the >> input signals. >> >> This mirrored logic is a kind of "super CMOS". >> >> Yes, this circuitry is twice as expensive as regular >> circuitry, but it has additional benefits: power side >> channel resistance, *noise resistance* -- including >> *radiation hardening*. >> >> Remaining problems: bit *changes* are still glaringly >> obvious; deep levels of combinational logic could >> get out of *sync*, unless locally synchronized or >> clocked. >> >> So far, this additional expense is easily doable, >> so I don't know why this mirroring couldn't be routine. >> >> At 02:39 PM 5/16/2018, Henry Baker wrote: >> >Constant power might not be too cool, but may be >> >unavoidable for certain calculations -- e.g., AES >> >encryption/decryption. It would be an interesting >> >theorem if constant power were the *only* solution. >> > >> >Some sort of "tri-stating with memory" might allow >> >lower power consumption for the vast majority of >> >wires that won't be changing on every clock cycle. >> >Having a wire stay at either "0" or "1" for long >> >periods of time doesn't cost anything, but changing >> >the state of a wire does cost the charging/discharging >> >of the capacitance of the wire. >> > >> >In this type of logic, the problem won't be "1's" or >> >"0's", but transitions: "+1", "-1". So the game may >> >be to have a double-width bus where half the bus gets >> >XOR'd with <secret> and the other half gets XOR'd >> >with not-<secret>, so that exactly length-<secret> >> >bits change. >> > >> >I think it may be possible to build systems having >> >both "secret" and "non-secret" bits; the only >> >constraint is that the instantaneous power is >> >independent of the secret bits -- i.e., the >> >power computation function is a *tautology* of >> >the secret bits. >> > >> >This leads us to consider a circuit design system >> >which outputs circuits both for the value to be >> >computed, as well as another circuit which computes >> >the power/energy consumed by the computation. It >> >is up to the circuit design system to make sure that >> >the two sets of circuits are in sync. >> > >> >While we're at it, we can also output a circuit >> >that computes the *timing* for the value-computing >> >circuit. For many situations, this circuit may be >> >trivial, but for others -- e.g., carry-propagation -- >> >this circuit may not be trivial. >> > >> >At 01:47 PM 5/16/2018, Tom Knight wrote: >> >>There are circuit topologies (as opposed to semiconductor technologies) >> that compute both the true and complement of every signal. To a very good >> first approximation, the power dissipated is constant in these circuits >> independent of the data flowing through them. The downside is that power >> dissipation is constant, but high. ECL logic is an early bipolar version, >> but similar topologies can be built with NMOS or CMOS technologies. It >> might be appropriate to use these topologies in security-sensitive >> applications. >> >> >> >>> On May 16, 2018, at 1:46 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> >>> I've been thinking about the *power* side-channel: >> >>> the ability to watch instantaneous power consumption >> >>> to guess what a computer is computing. >> >>> >> >>> Closely related: the chip temperature side-channel: >> >>> the ability to watch instantaneous temperature >> >>> distributions across a chip to guess what a computer >> >>> is computing. >> >>> >> >>> Note that simple power supply filtering doesn't >> >>> work well enough, as one might be able to watch >> >>> enough computation to still be able to discern >> >>> some amount of information. >> >>> >> >>> Since many computers would like to keep confidential >> >>> what they are computing, the question is raised: >> >>> >> >>> **Are there computer arithmetic circuits which draw >> >>> the same sequence of instantaneous power draws >> >>> *regardless* of the numbers being computed or moved?** >> >>> >> >>> For example, some computer circuit may draw slightly >> >>> more power when a "1" appears on a bus instead of a >> >>> "0". Under these conditions, it might make sense to >> >>> drive the bus with both the number and its binary >> >>> complement, in order to keep the power draw the same, >> >>> no matter what bit pattern is being operated on. >> >>> >> >>> Are there particular number representations and >> >>> arithmetic circuits (or even *boolean circuits*) >> >>> whose power consumption is indifferent ("oblivious") >> >>> to the input bit patterns? >> >>> >> >>> Note that CMOS typically utilizes both PNP and NPN >> >>> transistors in a complementary fashion. However, >> >>> due to semiconductor physics, these transistors are >> >>> not 100% complementary -- especially at high clock >> >>> rates -- and therefore they don't provide as much >> >>> obliviousness as one would like, so assume for >> >>> this conversation that we might still have to mirror >> >>> even CMOS gates. >-- >-- http://cube20.org/ -- http://golly.sf.net/ --

1 0

[math-fun] Golden ratio things
by James Propp 21 May '18

21 May '18

I'd like to understand better the connections between the following three things: (1) Zeckendorf representation of positive integers. (2) Beta-expansion of positive real numbers where beta is the golden ratio. (3) Symbolic encoding of points in the torus R^2 / Z^2 = (R/Z)^2 under the action of the toral automorphism associated with the matrix (1 1) (1 0) Can any of you enlighten me (or point me toward sources of enlightenment)? Thanks, Jim Propp

1 0

Re: [math-fun] Unsolved number theory problem
by Dan Asimov 20 May '18

20 May '18

Interesting — thanks, Frank! I wonder if there are large additional families of solutions of X^3 + Y^3 + Z^3 = K if the ring were expanded from the integers to some nice familiar unique factorization domain, like the Gaussian integers Z[i] or Eisenstein integers Z[exp(2πi/3)], or even the Hurwitz integral quaternions.* —Dan ————— * These are the quaternions that are integer linear combinations of the 24 unit quaternions {±1, ±i, ±j, ±k, (±1 ± i ± j ± k)/2}. These 24 form a group under quaternion multiplication known as the binary tetrahedral group and denoted by 2T. The group 2T can be seen as the inverse image p^(-1)(T), under the double-covering map p : S^3 —> SO_3 from the 3-sphere of unit quaternions to the rotation group SO_3 of 3-space R^3, of the 12 elements of the rotation group T of the regular tetrahedron. I.e., 2T = p^(-1)(T). ----- Frank Stevenson wrote: ----- I have spent considerable time looking into this and similar problems over the last couple of months. And think I should be able to give a short summary of the situation. There is a good basic introduction to the problem on Numberphile: https://www.youtube.com/watch?v=wymmCdLdPvM I think the best way to attack the problem computationaly is by using Noam Elkies method as done by Jahnel & al. : http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02168-6/S0025-57… This methods finds all "small" solutions via lattice reduction in time N (the upper search bound) More recently Sander G. Huisman has expanded the bound of the search to 10^15, but I suppose he is still using Jahnels old code: https://arxiv.org/abs/1604.07746 There are also ways to look for specific solutions, ex : http://www.ams.org/journals/mcom/2007-76-259/S0025-5718-07-01947-3/S0025-57… I have written code to do searches for specific solutions. But I still feel it is a bit hairy, especially the extraction of cube roots in finite fields, which is often claimed to be easy, but in practice it requires a hodgepodge of techniques from factorization, sieving, code for simple cases, finding roots of unity, Hensel lifting and for instance Tonelli-Shanks algorithms. My code works well enough to find solutions for related problems like I did here: http://www.maroon.dti.ne.jp/fermat/fourcubes1.html but is still work in progress. If I get to the point where I am happy with the code, it could for instance be be purposed for making a distributed BOINC style search effort for specific solutions such as 33 & 42 - but I am not quite there yet. /f On Fri, May 18, 2018 at 10:24 PM, Dan Asimov <dasimov(a)earthlink.net> wrote: Which integers S are the sum of three cubes: S = J^3 + K^3 + L^3 ??? (None of the form S == ±4 (mod 9), for instance.) Some low numbers are hard to find the J, K, L for, like: 30 = (−662037799708799)3 + 1908092688412843 + 6567116892545653 . The first S for which a solution is unknown is 33. The complete list of S < 1000 with no known solution (as far as I can tell) is as follows: 33 42 114 165 390 579 627 633 732 795 906 921 975 . —Dan -----

2 1

[math-fun] An obscure quartic equation
by Fred Lunnon 20 May '18

20 May '18

The quartic polynomial z^4 - 2*z^3 + z^2 - 2*z + 1 factorises completely into linear factors over finite field |F_p for p in set S = { 23, 127, 137, 151, 233, 239, 281, 359, 431, 449, 487, 673, 743, 751, 911, 953, 967, 977, ... } (all members with p < 1024). Can anything constructive be said about S ? For instance, Is S infinite? Does S contain subsets of form { p | p prime & p == a (mod b) } ? What (bounds on) asymptotic density has S , if any? WFL

2 2