July 2017 - mathfun@mailman.xmission.com

Re: [math-fun] Analog2Digital conversion using (mod range) sampling
by Henry Baker 22 Jul '17

22 Jul '17

Here are the slides: https://www.dropbox.com/s/0gozavqoc5so1cm/Unlimited%20Sampling.pdf?dl=1 At 12:22 PM 7/22/2017, Henry Baker wrote: >FYI -- > >It's not every day that someone gets around Shannon: > >https://www.dropbox.com/s/e7v4m4uhx8255tr/Unlimited%20Sampling.pdf?dl=1 > >Shannon's sampling theorem provides a link between the continuous and >the discrete realms stating that bandlimited signals are uniquely >determined by its values on a discrete set. This theorem is realized >in practice using so called analogÂtoÂdigital converters >(ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in >dynamic range. Whenever a signal exceeds some preset threshold, the >ADC saturates, resulting in aliasing due to clipping. The goal of this >paper is to analyze an alternative approach that does not suffer from >these problems. Our work is based on recent developments in ADC >design, which allow for ADCs that reset rather than to saturate, thus >producing **modulo samples**. An open problem that remains is: Given such >modulo samples of a bandlimited function as well as the dynamic range >of the ADC, how can the original signal be recovered and what are the >sufficient conditions that guarantee perfect recovery? In this paper, >we prove such sufficiency conditions and complement them with a stable >recovery algorithm. Our results not limited to certain amplitude >ranges, in fact even the same circuit architecture allows for the >recovery of arbitrary large amplitudes as long as some estimate of the >signal norm is available when recovering. Numerical experiments that >corroborate our theory indeed show that it is possible to perfectly >recover function that takes values that are orders of magnitude higher >than the ADC's threshold.

1 0

[math-fun] Analog2Digital conversion using (mod range) sampling
by Henry Baker 22 Jul '17

22 Jul '17

FYI -- It's not every day that someone gets around Shannon: https://www.dropbox.com/s/e7v4m4uhx8255tr/Unlimited%20Sampling.pdf?dl=1 Shannon's sampling theorem provides a link between the continuous and the discrete realms stating that bandlimited signals are uniquely determined by its values on a discrete set. This theorem is realized in practice using so called analogÂtoÂdigital converters (ADCs). Unlike Shannon's sampling theorem, the ADCs are limited in dynamic range. Whenever a signal exceeds some preset threshold, the ADC saturates, resulting in aliasing due to clipping. The goal of this paper is to analyze an alternative approach that does not suffer from these problems. Our work is based on recent developments in ADC design, which allow for ADCs that reset rather than to saturate, thus producing **modulo samples**. An open problem that remains is: Given such modulo samples of a bandlimited function as well as the dynamic range of the ADC, how can the original signal be recovered and what are the sufficient conditions that guarantee perfect recovery? In this paper, we prove such sufficiency conditions and complement them with a stable recovery algorithm. Our results not limited to certain amplitude ranges, in fact even the same circuit architecture allows for the recovery of arbitrary large amplitudes as long as some estimate of the signal norm is available when recovering. Numerical experiments that corroborate our theory indeed show that it is possible to perfectly recover function that takes values that are orders of magnitude higher than the ADC's threshold.

1 0

Re: [math-fun] Where do roots live in GF(2^k) ?
by Henry Baker 22 Jul '17

22 Jul '17

Thanks, Dan. The algebraic closure of the infinite sequence GF(p),GF(p^2),GF(p^3),... as described in the Wikipedia article is pretty ugly -- at least as described. I was hoping for something as elegant as the complex numbers with their usual topology. Perhaps I need to check back in about 300 years? At 10:08 AM 7/21/2017, Dan Asimov wrote: >Every field K Â if it does not already contain all the roots of polynomials in K[x] Â is a proper subfield of a larger field that is algebraically closed. > >E.g., see <https://en.wikipedia.org/wiki/Finite_field#Algebraic_closure>. > >I don't know how such an algebraic closure is usually visualized. > >But I believe that, for any prime p, the Galois group of [the algebraic closure of the finite field F(p)] over F(p) is isomorphic to the same thing for any other prime. > >ÂDan > >From: Henry Baker <hbaker1(a)pipelline.com> >Jul 21, 2017 9:06 AM: >----- > >OK, if I extend the rationals with the root alpha of an irreducible polynomial p[x], I can plot alpha on the complex plane; indeed, I can plot *all* of the roots of p[x] on the complex plane. So all of these "extension roots" live in the complex plane. > >Is there an analogous (single) place/field where all extension roots of GF(p) live -- i.e., a larger field which includes all of the extension fields of GF(p) ? > >There seems to be a problem, since there are many (isomorphic) ways to extend GF(p); perhaps these are all different in this larger field?

4 4

[math-fun] q-digamma(x,q) - digamma(x) expanded at q=1
by Bill Gosper 22 Jul '17

22 Jul '17

has polynomials in x as coefficients of (q-1)^n. See gosper.org/psi_q.png Plots are blue digamma overwritten by gold series approximation. For (q-)PolyGamma[n,...], just d^n/dx^n. QPolyGamma[3, 1/2, q] is phenomenally near π⁴ for .1<q<1: Table[QPolyGamma[3, 1/2, q] - π⁴, {q, .1`69, .9`69, .1`69}] // N Out[1343]= {-0.0000557992067391662, -3.46554182307681*10^-8, -8.95673115069408*10^-12, -3.02779751180959*10^-16, -2.86641755545745*10^-22, -4.2550061594941*10^-31, -1.32744226211741*10^-45, -1.41336365314375*10^-65} Intermediate 69 digit precision because of huge subtractive significance loss, as well as some sub-par Mathematica numerics. --rwg

1 1

Re: [math-fun] Where do roots live in GF(2^k) ?
by Dan Asimov 21 Jul '17

21 Jul '17

Every field K — if it does not already contain all the roots of polynomials in K[x] — is a proper subfield of a larger field that is algebraically closed. E.g., see <https://en.wikipedia.org/wiki/Finite_field#Algebraic_closure>. I don't know how such an algebraic closure is usually visualized. But I believe that, for any prime p, the Galois group of [the algebraic closure of the finite field F(p)] over F(p) is isomorphic to the same thing for any other prime. —Dan From: Henry Baker <hbaker1(a)pipeline.com> Jul 21, 2017 9:06 AM: ----- OK, if I extend the rationals with the root alpha of an irreducible polynomial p[x], I can plot alpha on the complex plane; indeed, I can plot *all* of the roots of p[x] on the complex plane. So all of these "extension roots" live in the complex plane. Is there an analogous (single) place/field where all extension roots of GF(p) live -- i.e., a larger field which includes all of the extension fields of GF(p) ? There seems to be a problem, since there are many (isomorphic) ways to extend GF(p); perhaps these are all different in this larger field? -----

1 0

[math-fun] Where do roots live in GF(2^k) ?
by Henry Baker 21 Jul '17

21 Jul '17

OK, if I extend the rationals with the root alpha of an irreducible polynomial p[x], I can plot alpha on the complex plane; indeed, I can plot *all* of the roots of p[x] on the complex plane. So all of these "extension roots" live in the complex plane. Is there an analogous (single) place/field where all extension roots of GF(p) live -- i.e., a larger field which includes all of the extension fields of GF(p) ? There seems to be a problem, since there are many (isomorphic) ways to extend GF(p); perhaps these are all different in this larger field?

1 0

[math-fun] Hoberman Flip-Out
by James Propp 17 Jul '17

17 Jul '17

I made a slo-motion video of a Hoberman Flip-Out wobbling between blue-in and blue-out states: https://m.youtube.com/watch?v=VC_KKTGWIOY Has anyone tried to analyze this phenomenon? Qualitatively it seems clear what's going on: centrifugal force (or whatever we're supposed to call it since it's not "really" a force) causes the thingies to spin out, and they overshoot, so then centrifugal force spins them the other way, and so on. But that's only a crude sketch of the dynamics. The Flip-Out has only one configurational degree of freedom, so it might be possible to solve it analytically and figure out the period of the oscillation (as a function of the position of the axis and the angular velocity), at least if it's rotating about some axis of symmetry. Jim Propp

2 1

[math-fun] Draft of my July 2017 blog post
by James Propp 17 Jul '17

17 Jul '17

I started writing a new draft titled "Swine in a Line" (a small piece of the picture that relates chip-firing to number representation systems) and would love to get your feedback. I plan on publishing it on Monday. Sorry for the shortness of notice. (Making the last two Barefoot Math videos took longer than I thought on account of equipment problems plus my being in England on holiday for over a week.) In addition to seeking the usual suggestions for how to make things clearer and livelier, I'm also seeking good links to good short web-pages on sandpiles and chip-firing that are in the same spirit as this article and aimed at the same readership. (I'm not planning to include a link to my Notices article with Levine on sandpiles; aside from it being too technical, it veers too much in the direction of fractal patterns, and although I touch on this indirectly via the Numerphile video, that's not really what I want to focus on here.) Please leave your feedback here: https://mathenchant.wordpress.com?p=1784&shareadraft=59690647cdd0e (keeping in mind that if you don't sign your comment I won't know who you, with the consequence that I won't be able to ask follow-up questions that your comments may elicit). Title: Swine in a Line Beginning: Last month I launched a new venture similar to my Mathematical Enchantments blog: a YouTube channel I'm calling Barefoot Math. The first few videos are about a game I invented that I call Swine in a Line. It's a game with an easy-to-describe but not-so-easy-to-find winning strategy, and the challeng... Read more: https://mathenchant.wordpress.com?p=1784&shareadraft=59690647cdd0e Thanks, Jim

2 2

[math-fun] Hacking binary finite fields on Intel processors
by Henry Baker 17 Jul '17

17 Jul '17

FYI -- Almost everything you ever wanted to know about bit-hacking on Intel processors for implementing binary finite fields. Yes, squaring and square roots are easy -- even in a polynomial (rather than a normal basis) representation. Aranha talks about multiple-precision operations on 64-bit and 128-bit registers, so we're talking about big fields here with hundreds and thousands of bits. Notice that the number of views of this video today is only *41* (including mine)! Clearly, it is far easier to get around crypto than to break crypto; only 41 people cared enough to find out what's going on! https://www.youtube.com/watch?v=Zr7htuOurI4 Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets Microsoft Research 41 views Published on Jul 27, 2016

2 1

[math-fun] Do this one, Mascheroni, and you can stick the feather back in your cap.
by Bill Gosper 17 Jul '17

17 Jul '17

Out[1028]= Sum[((-1)^n*QPolyGamma[0, -(Log[-(n/2)]/Log[2]), 1/2])/ n, {n, 1, Infinity}] == (-1 + EulerGamma - Log[2])*Log[2] In[1029]:= N@% Out[1029]= True

1 0