老王v破解版

In this post, I’d like to explain a proof of the Law of Quadratic Reciprocity based on properties of Lucas polynomials. (There are over 300 known proofs of the Law of Quadratic Reciprocity in the literature, but to the best of my knowledge this one is new!)

In order to keep this post as self-contained as possible, at the end I will provide proofs of the two main results (Euler’s criterion and the Fundamental Theorem of Symmetric Polynomials) which are used without proof in the body of the post.

Lucas polynomials

The sequence of Lucas polynomials is defined by L_0(x)=2, L_1(x)=x, and L_n(x)=xL_{n-1}(x)+L_{n-2}(x) for 国外免费加速器下载

The next few terms in the sequence are L_2(x)=x^2+2, L_3(x)=x^3+3x, L_4(x)=x^4 + 4x^2 + 2, and L_5(x)=x^5+5x^3+5x.

By induction, the degree of L_n(x) is equal to n. The integers L_n(1) are the Lucas numbers, which are natural “companions” to the Fibonacci numbers (see, e.g., 国外免费加速器手机版).

Edouard Lucas (source: Wikipedia)

The polynomials 免费加速器看国外视频

It’s easy to see that for n odd, L_n(x) is divisible by x and L_n(x)/x has only even-power terms. Thus L_n(x)/x = H_n(x^2) for some monic integer polynomial H_n(x) of degree (n-1)/2. We will be particularly interested in the polynomials H_p(x) for p prime.

If n is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of x) in 蚂蚁海外加速器永久免费版 is equal to 蚂蚁海外加速器永久免费版. In particular, for n odd we have H_n(0)=n.

Continue reading

老王v破解版

Everyone who studies elementary number theory learns two different versions of Fermat’s Little Theorem:

Fermat’s Little Theorem, Version 1: If 海外永久免费软件加速器 is prime and a is an integer not divisible by 免费跨国加速器, then 国外免费加速器.

Fermat’s Little Theorem, Version 2: If 蚂蚁海外加速器永久免费版 is prime and a is any integer, then a^{p} \equiv a \pmod{p}.

as well as the following extension of Version 1 of Fermat’s Little Theorem to arbitrary positive integers n:

Euler’s Theorem: If 免费跨国加速器 is a positive integer and (a,n)=1, then 海外永久免费软件加速器, where \phi is Euler’s totient function.

My first goal in this post is to explain a generalization of Version 2 of Fermat’s Little Theorem to arbitrary 蚂蚁vp(永久免费). I’ll then explain an extension of this result to m \times m integer matrices, along with a slick proof of all of these results (and more) via “combinatorial zeta functions”.

Continue reading

老王v破解版

Today is the 10th anniversary of the death of Martin Gardner. His books on mathematics had a huge influence on me as a teenager, and I’m a fan of his writing on magic as well, but it was only last year that I branched out into reading some of his essays on philosophy, economics, religion, literature, etc. In this vein, I highly recommend “The Night Is Large”, a book of collected essays which showcases the astonishingly broad range of topics about which Martin had something interesting to say. It’s out of print, but it’s easy to find an inexpensive used copy if you search online.

Thinking back on my favorite Martin Gardner columns, my all-time favorite has to be the April 1975 issue of Scientific American. In that issue, Martin wrote an article about the six most sensational discoveries of 1974. The whole article was an April Fools’ Day prank: among the discoveries he reported were a counterexample to the four-color problem and an artificial-intelligence computer chess program that determined, with a high degree of probability, that P-KR4 is always a winning move for white. The article also contained the following:

Continue reading

老王v破解版

Usually my blog posts are rather tightly focused, but today I’d just like to post a few stream-of-consciousness thoughts.

(1) My blog was recently 永久免费国际加速器 in the AMS Blog on Math Blogs. Perhaps by mentioning this here I can create some sort of infinite recursion which crashes the internet and forces a reboot of the year 2020.

Continue reading

老王v破解版

In 免费加速国外软件, I recalled a discussion I once had with John Conway about the pros and cons of different systems for mentally calculating the day of the week for any given date. In this post, I’ll present two of the most popular systems for doing this, the “Apocryphal Method” [Note added 5/3/20: In a previous version of this post I called this the Gauss-Zeller algorithm, but its roots go back even further than Gauss] and Conway’s Doomsday Method. I personally use a modified verison of the apocryphal method. I’ll present both systems in a way which allows for a direct comparison of their relative merits and let you, dear reader, decide for yourself which one to learn.

Continue reading

老王v破解版

My previous post was about the mathematician John Conway, who died recently from COVID-19. This post is a tribute to my Georgia Tech School of Mathematics colleague Robin Thomas, who passed away on March 26th at the age of 57 following a long struggle with ALS. Robin was a good friend, an invaluable member of the Georgia Tech community, and a celebrated mathematician. After some brief personal remarks, I’ll discuss two of Robin’s most famous theorems (both joint with Robertson and Seymour) and describe the interplay between these results and two of the theorems I mentioned in my post about John Conway.

Continue reading

老王v破解版

John Horton Conway died on April 11, 2020, at the age of 82, from complications related to COVID-19. See 能上国外网的免费加速器 from Princeton University for an overview of Conway’s life and contributions to mathematics. Many readers of this blog will already be familiar with the Game of Life, surreal numbers, the Doomsday algorithm, monstrous moonshine, Sprouts, and the 15 theorem, to name just a few of Conway’s contributions to mathematics. In any case, much has already been written about all of these topics and I cannot do justice to them in a short blog post like this. So instead, I’ll focus on describing a handful of Conway’s somewhat lesser-known mathematical gems.

Continue reading

海外永久免费软件加速器

My friend Joshua Jay, who is one of the world’s top magicians, emails me from time to time with math questions. Sometimes they’re about card tricks, sometimes other things. Last night he sent me an excellent question about COVID-19, and I imagine that many others have wondered about this too. So I thought I’d share my response, in case it’s helpful to anyone.

JJ: Since the government is predicting between 100k – 240k deaths from COVID-19, let’s for argument’s sake split the difference and call it 170k projected deaths. They’re ALSO telling us they believe the deaths will “peak” something like April 20th. Am I wrong in assuming, then, that if we assume 170k total deaths, and the halfway point is a mere two weeks away, then they’re projecting 85k deaths before (and after) April 20th?

When I start to think about the idea of of 85k deaths between now and April 20th, and we’ve only experienced 5k so far, it means that 80k people are projected to die in the next two weeks. Surely that can’t be correct, or else it would be dominating the news cycle, right?

I’m not asking whether you think those projections are accurate… I’m just trying to wrap my head around the relationship between total projected deaths (whatever it is) and the projected peak of the curve. 

Continue reading

Zero Knowledge Identification and One-Way Homomorphisms

Imagine logging into a secure web server which, instead of asking you to type in your password, merely asks you questions about your password until it’s convinced that you really do know it and therefore are who you say you are. Moreover, imagine that your answers to the server’s questions provide no information whatsoever which could be used by a malicious hacker, even if all communications between you and the server are being intercepted. Finally, imagine that the server in question not only does not store any information about your password, it has never at any point asked you for information about your password.

绝地求生吃鸡加速器哪个好,吃鸡高性价加速器推荐_排行榜123网:2021-10-16 · 绝地求生吃鸡加速器哪个好,吃鸡高性价加速器推荐 要问现在最火的游戏是什么,《绝地求生》当然不让,被玩家被称为吃鸡。然而因为这是国外的游戏,还没有国服,所以需要使用加速器,才能流畅的吃鸡,避免掉线卡顿。那么吃鸡加速器哪

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

Continue reading

Interlacing via rational functions and spectral decomposition

First of all, I’d like to express my sympathies to everyone who is enduring hardships due to COVID-19. Stay well and be strong.

In this previous post, I discussed two important classical results giving examples of polynomials whose roots interlace:

Theorem 1: The roots of a real-rooted polynomial and its derivative interlace.

Theorem 2: (Cauchy’s interlacing theorem) The eigenvalues of a real symmetric matrix interlace with those of any principal minor.

In this post, I’d like to explain a general method, based on partial fraction expansions of rational functions, which gives a unified approach to proving Theorems 1 and 2 and deserves to be better known.

Continue reading

Complementary sets of natural numbers and Galois connections

In this post, I’d like to discuss a beautiful result about complementary sets of natural numbers due to Lambek and Moser. I first learned about their theorem as a high school student (from Ross Honsberger’s delightful book “Ingenuity in Mathematics”), but it’s only more recently that I learned about the “Galois” connection.

To motivate the discussion, consider the following question. Let F = \{ 0,1,4,9,16,25,\ldots \} be the sequence of squares, and let 国外免费加速器手机版 be its complement in {\mathbb N} = \{ 0,1,2,3,\ldots \}. What is the 浏览外网的免费加速器 term of the sequence 免费跨国加速器? In other words, can we give a formula for the n^{\rm th} non-square? One might imagine that no simple formula exists, but in fact Lambek and Moser showed that the n^{\rm th} non-square is equal to n + \{ \sqrt{n} \}, where 免费加速国外软件 denotes the closest integer to x. Similarly, if T = \{ 0,1,3,6,10,\ldots \} denotes the set of triangular numbers, the n^{\rm th} element of the complement of T is equal to n + \{ \sqrt{2n} \}.

Figure by Scott Kim
Continue reading

Lorentzian Polynomials II: Applications

In this previous post, I described the basic theory of Lorentzian polynomials d’après Brändén and Huh. Now I’d like to describe some of the powerful applications of this theory, culling together results from papers by several different sets of authors. Our first application will be Mason’s Ultra-Log-Concavity Conjecture from 1972, established independently by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant in 2018.

Theorem: Let M be a matroid on n elements, and let I_k(M) denote the number of independent sets of size k in M. Then the sequence I_k(M) is ultra-log-concave.

A special case of this result (which seems to be no easier to prove than the general case) is the following: Let E be a set of n vectors in some finite-dimensional vector space, and let I_k denote the number of k-element linearly independent subsets of 蚂蚁海外加速器永久免费版. Then the sequence I_k is ULC.

Continue reading

Lorentzian polynomials I: Theory

I’m organizing a reading seminar this semester on Lorentzian polynomials, mainly following 浏览外网的免费加速器 by Brändén and Huh but also covering some of the work of Anari et. al. In this post, I’d like to give a quick introduction to this active and beautiful subject. I’ll concentrate on the basic theory for now, and in a follow-up post I’ll discuss some of the striking applications of this theory.

One major goal of the theory of Lorentzian polynomials is to provide new techniques for proving that various naturally-occurring sequences of non-negative real numbers a_k are log-concave, meaning that a_k^2 \geq a_{k-1} a_{k+1} for all k. More generally, the authors consider homogeneous multivariate polynomials p(x_1,\ldots,x_n) with non-negative coefficients and study certain natural extensions of log-concavity to this setting. (For some background on log-concave sequences, see this survey paper which I wrote for the Bulletin of the AMS.) So let me begin by introducing two “classical” methods for proving (an even sharper version of) log-concavity of the coefficients of certain polynomials.

Continue reading

境外用户福音:海外专线节点免费试用!-网易UU网游加速器官网:2021-1-11 · 网易UU加速器,采用网易自主研发极速引擎,顶级IDC集群,全线高端刀片服务器!为网游用户解决延迟、掉线、卡机等问题,让你游戏更爽快!国服加速永久免费!海外直连专线,外服游戏加速效果业界顶尖!支持魔兽世界、LOL英雄联盟、DNF地下城与勇士、CF穿越火线、DOTA2、坦克世界、梦三国 …

A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in 能上国外网的免费加速器 by Paul Pollack.)

网易UU网游加速器——玩出超快感,外服加速72小时免费:网易UU加速器,采用网易自主研发极速引擎,顶级IDC集群,全线高端刀片服务器!为网游用户解决延迟、掉线、卡机等问题,让你游戏更爽快!国服加速永久免费!外服加速72小时免费试用。海外直连专线,外服游戏加速效果业界顶尖!支持加速绝地求生、H1Z1、GTA5、CSGO,以及LOL英雄联盟、DNF地下城 …

海外永久免费加速器

Indeed, there is precisely one term 永久免费国际加速器 for each integer 海外加速器免费下载 on the left-hand side, and the same is true for the right-hand side (consider separately the cases where p \mid n but 海外永久免费加速器, q \mid n but p \nmid n, and pq \mid n). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc 海外永久免费加速器:

\frac{z^2}{1-z} = \frac{z^p}{1-z^p} + \frac{z^q}{1-z^q} - \frac{z^{pq}}{1-z^{pq}}.

This is impossible, however, as we see by letting 国外免费加速器手机版 approach a primitive pq^{\rm th} root of unity, since each term stays bounded except for \frac{z^{pq}}{1-z^{pq}}, which tends to infinity.

Continue reading

The Drunkard’s Walk and Catalan Numbers

In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers.  This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.

In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):

A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is 蚂蚁vp(永久免费) (and therefore his probability of taking a step toward the cliff is 免费加速器看国外视频). What is the probability that the man will eventually fall off the cliff?

Continue reading