Wikipedia:Reference desk/Archives/Mathematics/2022 December 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 4

Discrete analogs of PDE

Someone on mathoverflow writes:[1]

aren't there a whole bunch of neat results in combinatorics on discrete analogs of PDE? I'm thinking, for example, of Stone's theorem for the discrete Schrodinger equation; the characterization of graph spectra; and how some solutions of the discrete Laplacian/discrete Helmholtz/discrete modified Helmholtz lead to special instances of ADE Dynkin diagrams.

Can someone explain that paragraph? Web search on Stone's theorem mostly found stuff about Stone-Čech compactification which is unrelated to the topic. I found the article about the ADE classification which I hadn't heard of before. I've also found some references to a discrete NLSE but I'm wondering if something like an inverse problem has been considered: given an arbitrary PDE, is there a combinatorial analog? Can complex (etc.) valued fields come out of such analogs? This question is inspired by wondering whether quantum mechanics could be the continuum limit of a discrete process. Thanks. 2601:648:8200:990:0:0:0:497F (talk) 01:49, 4 December 2022 (UTC)

I'm not familiar with any of these, but here are three references to statements that are labelled "Stone's theorem": [2], [3], [4]. At a cursory glance, the first two seem equivalent while the third is obviously strongly related; perhaps these are the two sides of a stronger equivalence. The Schrödinger equation can be discretized in various ways.^[5] Stone's theorem can be applied to the Schrödinger equation,^[6] but to apply it to a discretization one would need to develop a discrete variant of Stone's theorem. I doubt that the quantum weirdness of "spooky action at a distance" can arise as the limit of a non-spooky process. BTW, we do not yet (hint hint) have an article on the concept of Continuum limit, although many of our articles (at least 43) use the term.  --Lambiam 10:51, 4 December 2022 (UTC)

Thanks. Maybe continuum limit could redirect to scaling limit. 2601:648:8200:990:0:0:0:497F (talk) 04:17, 5 December 2022 (UTC)

Even stronger, I've moved Scaling limit to the new title of Continuum limit.  --Lambiam 13:49, 5 December 2022 (UTC)

Erm, hmm, ok I guess. I have the impression that continuum limit is a physicist's term, while mathematicians say scaling limit to mean the same thing. Because physics is not presumed to have a true contiuum except as a limit, while the continuum is a perfectly good mathematical object. John Baez has written about "struggles with the continuum" in physics.[7] 2601:648:8200:990:0:0:0:497F (talk) 04:31, 6 December 2022 (UTC)

Btw my thought about quantum mechanics is partly from looking at some of the links from causal dynamical triangulation (CDT). CDT is a successor of dynamical triangulation (DT) which was a similar idea, where they considered taking a lot of little tiny triangles under a Euclidean metric. It failed because the resulting space either "polymerized" (converged to a lot of thin strands, i.e. 1-dimensional) or "crumpled up" (became infinite dimensional). By switching to a Lorentzian metric, lo and behold they got 3+1 spacetime like in GR, so they figured they must be onto something. But if "crumpling" can be seen as approaching an infinite dimensional space, that makes me wonder about the Hilbert space of QM. Spooky action at a distance (entanglement) after all results from the wave function of the entangled system living n the tensor product of the component systems, i.e. a space of very high dimensionality. I'd like to understand better whether "crumpling" can lead to something like that. 2601:648:8200:990:0:0:0:497F (talk) 04:29, 5 December 2022 (UTC)

A proof by mathematical induction.

Dear member,

I have written a proof of Fermat's little theorem.

I am quit insecure.

It would please me if a mathematician reviews my proof and lets me know whether my proof is valid and correct.

I'm grateful for any help I get.

Thanks in advance Wim Coenen (talk) 19:50, 4 December 2022 (UTC)

It is a good standard to explain the nature of all variables used (are they integers, matrices, or what?), and to clearly state what is given and what is to be proved. So it should be stated explicitly that $A$ is an integer and that $p$ is a prime number. The first line, an inequation, uses a variable $a$ that is unexplained and does not appear elsewhere. The intention is that the inequation holds for all integers $a$, but this is not obvious from the notation. It is OK to state in words that $A$ is not divisible by $p$, but one can also use the "does not divide" notation $p\not \mid A$ (see Divisor § Definition) or use $A\not \equiv 0{\pmod {p}}.$ Also, if other mathematicians are meant to be able to follow a proof, it helps if standard terminology is used. What you call "Induction step 1" is normally called the "base case" (see the article on mathematical induction).

The proof appears to apply mathematical induction on $A$, since $A+1$ is substituted for $A$. The conclusion of the induction step is that $(A+1)^{p-1}-1$ is divisible by $p$. But in the base case it was already proved that $A^{p-1}-1$ is divisible by $p$ for all $A,$ so we knew this already. The problem is that this is only proved for the case that $p=2.$

Now, except for one case, if $p$ is prime, $p+1$ is not prime. It is therefore impossible to prove that a statement is valid for all prime numbers $p$ by mathematical induction on $p.$  --Lambiam 01:52, 5 December 2022 (UTC)

That's what confused me at first sight -- it's not clear what the induction variable is. What seems to be the base case (called "Induction step 1") says it's proving something when p=2, so it sounds like p is going to be the induction variable. But then the next step substitutes A+1 for A, so it looks like A is the induction variable. If A is the induction variable, then the base case should be proving the equality for A=1, but I don't see such a step anywhere in the proof.

There are some other confusing things. The base case sets A=2k+1 for some unexplained reason. Does the proof only work for odd A? In "Induction step 3" a variable k is used as an index of summation. It is at least confusing to reuse the variable name k like this. Also, I didn't follow all the steps in detail, but I don't see where you use the fact that p is prime. If the proof doesn't depend on p being prime, then it's obviously wrong. CodeTalker (talk) 02:46, 5 December 2022 (UTC)

The attempted proof does not made it explicit which variable, $A$ or $p$, is the induction variable, making it hard to understand the intention. If $p$ is the induction variable, with $p=2$ as the base case, $A\not \equiv 0~~({\text{mod}}~p)$ implies that in the proof of the base case $A$ can be written in the form $2k+1.$ It seems as if both variables vie for playing the role.  --Lambiam 10:50, 5 December 2022 (UTC)

I found it hard to understand your proof, and I don't know how Fermat proved it. But these days we think of this theorem as an immediate consequence of Lagrange's theorem (group theory), which might have historically come later than Fermat's proof. The multiplicative group of integers mod p has p-1 elements, so the subgroup generated by any element must have order dividing p-1. In fact if the "big" group is modulo a composite number N whose factorization you know, you can compute the size of the subgroup as Euler's totient function of N. That means you can compute k'th roots in that group etc. But if you don't know the factorization you can't compute the totient (since factorizing numbers is supposed to be hard, but if you can compute the totient you can recover the factorization). That is the basis of the RSA cryptosystem. 2601:648:8200:990:0:0:0:497F (talk) 04:40, 5 December 2022 (UTC)

Fermat stated his theorem (without proof) in 1640,^[8] while Lagrange's theorem of which it is an easy corollary first appeared in 1770–71.^[9]  --Lambiam 11:03, 5 December 2022 (UTC)

p^(p-1)-1 is not divisible by p so the induction should fail for A going from p-1 to p. Anyway there's obviously some bug there in the reasoning. It can be tidied up but needs the tidying up to be explicit. NadVolum (talk) 12:40, 5 December 2022 (UTC)

I doubt that this proof attempt can be repaired by "tidying up".  --Lambiam 13:58, 5 December 2022 (UTC)

They just need to do that A^p - A is divisible by p instead. They assumed A+1 was not a multiple of p in the last division. In which case they should assume A could also possibly be a multiple of p at the start but it shouldn't be a big change. It just needs to be done cleanly with a bit of explanation. NadVolum (talk) 14:21, 5 December 2022 (UTC)

I think you are right. The following is the essence of Euler's proof by induction, which may have been the essence of the attempted proof:

Lemma. Let $p$ be a prime number. Then ${\binom {p}{k}}\equiv 0{\pmod {p}}$ for $1\leq k\leq p-1.$

Proof. Writing ${\binom {p}{k}}={\frac {p!}{k!(p-k)!}},$ we see that each factor of the denominator $k!(p-k)!$ is less than $p$, and so the factor $p$ of the nominator cannot be cancelled.

The binomial theorem gives us an immediate corollary:

$(a+1)^{p}\equiv a^{p}+1{\pmod {p}}.$

Using this corollary, it is an almost trivial exercise to use induction on $a$ to prove $a^{p}\equiv a{\pmod {p}}.$  --Lambiam 14:36, 5 December 2022 (UTC)

A good example of what that proof should look like! Thanks for that link - I like having a number of differenet proofs of the same thing 😀 NadVolum (talk)