- mathfun@mailman.xmission.com - mailman.xmission.com

[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 19 May '18

19 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

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

19 May '18

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.

8 10

[math-fun] Unsolved number theory problem
by Dan Asimov 19 May '18

19 May '18

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

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

18 May '18

Thanks, Mike. This is indeed the type of attack that computers processing private information can be subjected to. Paul Kocher has done some terrific work, and I've watched a number of his talks on YouTube. Much of his earlier work had to do with watching crypto algorithms on smart cards and computers. More recently he's been active on Spectre (cache timing side-channel) vulnerability. However, it has become clear (!) that nearly *all* computing has some privacy aspects, so nearly all computers & computations will have to start incorporating resistance to side-channel attacks such as timing (which may be "visible" from thousands of miles away) to power and electromagnetic side-channels, which may be visible for tens of meters -- e.g., it might even be possible to hack a Wifi router's radio receiver to detect certain electromagnetic emissions from a nearby laptop. There may be severe performance consequences as a result of such side-channel resistance: greatly increased compute times, greatly increased compute energies, much more expensive shielding, etc. Nevertheless, just as our automobiles have had to incorporate crash-resistance, fail-safe and ABS brakes, and other safety measures, computers will have to have analogous improvements. At 02:45 PM 5/16/2018, Mike Stay wrote: >Paul Kocher did lots of research along these lines. >https://www.rambus.com/introduction-to-differential-power-analysis-and-rela… > >On Wed, May 16, 2018 at 3:39 PM, Henry Baker <hbaker1(a)pipeline.com> 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. > >-- >Mike Stay - metaweta(a)gmail.com >http://www.math.ucr.edu/~mike >http://reperiendi.wordpress.com

2 2

[math-fun] D. Wilson
by James Propp 17 May '18

17 May '18

Does anyone have updated contact information for* wilson(a)ctron.com*? Thanks, Jim Propp

3 3

[math-fun] Who wrote this paper?
by Henry Baker 17 May '18

17 May '18

Well, I'm not 100% certain, but *someone* must have written a paper *sometime* about positional number systems using an *algebraic* and/or *algebraic integer* radix and integer numerals. Knuth? Knuth? Anyone? Anyone? Several interesting things: If p(r) is the minimal polynomial for r, and deg(p)=n, then we can express r^n in terms of lower powers of r, and thus there is some possible redundancy in the representations. Also, if n>1, then there are multiple r's satisfying p(r)=0, so we have to relate representations using r and r', s.t. p(r)=p(r')=0. Clearly, complex number systems of the 1+i type qualify, but I don't recall any such systems with n>2. Also, cyclotomic polynomials have the same unfortunate property that base-(e^i) numbers have -- namely, it is a lot more difficult to represent large numbers.

8 15

[math-fun] The Muffin Problem -- my gang solved one of your conjectures
by William Gasarch 17 May '18

17 May '18

In Jan 2009 this email list discussed the Muffin Problem which was due to Alan Frank: You have m muffins to give out to s students. You want to give everyone m/s muffins. How to divide-and-distribute and maxmize the min piece. We let f(m,s) be the size of the smallest piece in the opt procedure. I saw the problem at Gathering for Gardner 2016 and worked on it for two years (unaware of the discussions on this list). I read over all the discussion done here (thanks to Jim Propp's arxiv of it) and there was not much overlap: 1) Erich Friedman prove f(m,s) = (m/s)f(s,m) 2) Veit Elser proved that f(m,s) can be computed by a Mixed Int Program 3) Someone conjectured that for m>s f(m,s) \ge 1/3. That last conjecture we proved! Here are pointers to where to look for our work 1) Conference proceeding for FUN with Algorihtms: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/ffmuff.pdf The appendix has the proof of f(m,s) \ge 1/3 2) slides on a talk I give on the problem: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/muffintalk.pdf 3) the long long papers on it on arxiv (not recommended- but one day it will be better) https://arxiv.org/abs/1709.02452

1 0

[math-fun] Draft of May 2018 blog post
by James Propp 14 May '18

14 May '18

I started writing a new draft titled "Time and Tesseracts" and would love to get your comments, whether I receive them before or after I publish the essay on my blog (late on the 16th or early on the 17th). Sorry for the many rough spots near the end, which I plan to work on over the next couple of days. Even after the 17th I'm likely to continue to tinker with the piece, and feedback will be gratefully acknowledged. (I'm aware that the footnote-links don't work, but there are probably lots of other glitches I'm unaware of.) Please leave your feedback here: https://mathenchant.wordpress.com?p=2303&shareadraft=5afa4b14f3cc0 but be aware that the feedback-link is a "party line"; if I receive an unsigned comment there, all I'll know is that it's from some math-fun subscriber. (Which may be your intention. But if you have a comment I want to act upon, I may have some follow-up questions for you, such as "Is the following rewrite less terrible?", which I won't be able to ask you if I don't know who you are!) Title: Time and Tesseracts Beginning: "The fourth dimension became a thing you talked about, without knowing what it meant." --- Marcel Duchamp 16th-century scholar Gerolamo Cardano1 thought the fourth dimension was contrary to Nature. 17th-century thinker John Wallis2 thought the very idea of it was monstrous. And now 21st century virt... Read more: https://mathenchant.wordpress.com?p=2303&shareadraft= 5afa4b14f3cc0 Thanks, jamespropp

1 0