Write An Equation And Express The Product In Standard: Fill & Download for Free

Convolution is one of those very, very fundamental operations in mathematics that show up all over the place in all manner of different guises. The usual general setting goes something like this: suppose that I consider integrable functions on some measure space [math]X[/math]—that is, I have complex-valued functions [math]f: X \rightarrow \mathbb{C}[/math] that I can “integrate” in some sense. We’ll also ask that we can “add” elements of [math]X[/math] in some nice way. (For those familiar with such terms: we ask that [math]X[/math] be a locally compact abelian group and we take the Haar measure.) Then we can define the convolution of any two functions [math]f,g: X \rightarrow \mathbb{C}[/math] as the function[math]\displaystyle (f*g)(x) = \int_X f(y)g(x - y) \ \text{d}\mu(y). \tag*{}[/math]Don’t worry if you haven’t seen the [math]\text{d}\mu(y)[/math] notation before—it’s essentially saying that we have something that is kind of like the Riemann integral that you are likely familiar with, but it doesn’t have to be it on the nose. Some examples:Taking [math]X = \mathbb{R}^n[/math] (that is, [math]n[/math]-dimensional Euclidean space) with the usual notion of addition and integration.Taking [math]X = \mathbb{Z}[/math] (that is, the integers) with the usual notion of addition but with Riemann integration replaced with summation over all integers. (So, [math]\int_X f(y)g(x - y) \ \text{d}\mu(y)[/math] becomes just [math]\sum_{m = -\infty}^\infty f(m)g(n - m)[/math].)Taking [math]X = (0,\infty)[/math] (that is, all positive real numbers) with addition replaced by multiplication and with integration with respect to [math]\text{d}x[/math] replaced with integration with respect to [math]\frac{\text{d}x}{x}[/math].Without even meaning to, I have written about convolution before.In my answer to What is the strangest exception to a rule that you know?, I discussed the very bizarre Borwein integral. As I mentioned there, the way to understand why it has the weird properties that it has is via Fourier transforms and convolution.In my answer to What is a Green function mathematically and intuitively speaking? How many are there and what are the different applications of these functions in everyday life or in science?, I showed how convolutions with Green functions are useful for solving various partial differential equations of interest in physics, engineering, and other sciences.In my answer to What is the Mobius Inversion function. How does it apply in number theory?, I made use of the Möbius inversion theorem to neatly describe cyclotomic polynomials. However, if you look carefully at what this theorem says, it is really a question about convolutions.In my answer to Why is the gamma function designed in such a way that its argument is shifted down by 1 compared to the factorial function for positive integers?, I gave a different application to number theory: it turns out the most natural way to think about the gamma function is to think about it as a specific type of convolution known as a Mellin transform. The Mellin transform pops up frequently in the context of automorphic forms, where it is useful for getting various number-theoretic identities.There are all sorts of other answers that you could write about why convolutions are interesting. One thing to explore is their connection with the Fourier transform—specifically, the Fourier transform of the convolution of two functions is the product of their Fourier transforms! So, if you care about Fourier analysis, you should expect to see convolutions to pop up. This comes up in the theory of partial differential equations and also, as an example, in quantum mechanics. The reason is the following: in QM, the Fourier transform is what switches between expressing the wavefunction as a function of position and expressing the wavefunction as a function of momentum. If you have a product of wavefunctions, then it will become a convolution in the other formulation.Here is another, entirely separate, application of convolution: optics and deconvolution. Actually, let’s first start with something a bit simpler: Gaussian blur. This is a tool that exists in essentially every photo-editing software in existence. What does it do? Well… it blurs things.But, you know, how does that actually work under the hood? As it turns out, what is essentially happening is a convolution. Think of a picture as a function—to every pixel, it returns a color, expressed as a vector [math](R,G,B)[/math] of real numbers. What Gaussian blur does is it takes the components of this function and convolves them with a Gaussian distribution like[math]\displaystyle \frac{1}{2\pi \sigma^2} e^{-(x^2 + y^2)/(2\sigma^2)} \tag*{}[/math]where [math]\sigma[/math] is some positive real number known as the standard distribution. The output is your blurred picture. (The way this is actually implemented in software might be a little bit different, but this is what is happening mathematically.) If the standard distribution is very small, then this convolution will return something almost identical to the original picture because, in the convolution, pixels far away from the one you are looking at are given very little weight. If the standard distribution is large, they are weighted more heavily, and the output picture looks much more blurred as a result.Here’s the kicker: this same idea can be run in reverse. Suppose that you are trying to build a telescope. You want it to give you the clearest view of the distant stars as possible, but you have a problem: if you build it on Earth, then the atmosphere warps light, leading to blurring. How do you fix it? Well, one obvious solution is to put the telescope in space—most famously, this is what was done for the Hubble Space Telescope. But putting anything into orbit is eye-wateringly expensive and astrophysicists are not known for having deep pockets. So what can you do?Well, one option is to recognize that the blurring that happens from light passing through the atmosphere can be viewed as a convolution with some kind of function [math]f(x,y)[/math]—that is, if the actual image would be a function [math]P(x,y)[/math], then what you actually get through the telescope is [math](P*f)(x,y)[/math]. Well, if you can work out what [math]f[/math] is, then you can do some variant of the following.Take the Fourier transform [math]\widehat{P*f}[/math] of [math]P*f[/math]. Since Fourier transform turns convolution into products, this is actually just [math]\hat{P}\hat{f}[/math].Divide this by [math]\hat{f}[/math], yielding just [math]\hat{P}[/math].Take the inverse Fourier transform to get [math]P[/math]!This is the fundamental idea behind deconvolution: if you can work out how your conditions are distorting your image, you can automatically remove this distortion. Of course, figuring out what this distortion is isn’t easy in general, but there are many useful cases where you can get a decent approximation either via theoretical predictions or by studying what happens to some images where it is known what they look like prior to the blurring—note that, since Fourier transform turns convolutions into products, you can use similar reasoning to that above to work out the blurring function [math]f[/math].Here is this process applied to our example from before. If you look very closely, you will notice that the conversion is not quite perfect—there are some artifact introduced from the fact that we are trying to represent a continuous, real-valued concept in terms of discrete functions that a computer can actually work with and, more importantly, by the fact that rather than working on the entire plane, we are truncating to a smaller rectangle inside it. Even so, it is an immensely useful tool in a variety of settings.

There are many, many formulas for prime numbers, despite the common answer "there isn't any such formula" being given quite often. Let me show you a few, but before answering this question, let's answer a simpler one which is obviously a prerequisite: what is a formula?Here are some examples.1. In how many ways can [math]n[/math] people stand in line? Answer: [math]n![/math].2. What's the expected number of coupons you need to collect until you find all [math]n[/math] distinct coupons? Answer: [math]n\sum\limits_{i=1}^n\frac{1}{i}[/math].3. What's the [math]n[/math]th prime number? Two possible answers: we can denote this by [math]p_n[/math], and we can also write a tiny computer program that produces [math]p_n[/math] as output given [math]n[/math] as input.I know what you're thinking. "One of these things is not like the others". You're thinking that my answer to question 3 isn't a formula, it's either an ad hoc notation which is cheating, or a computer program which is also cheating.My job now is to show you this is false.Let's look at question 1. Why is "[math]n![/math]" a valid formula? Well, because everyone knows what "factorial" is, right? You just multiply all the numbers from 1 to [math]n[/math] and that's your answer. But you see, this "factorial" thing is an arbitrary notation we invented to make certain formulas easy to write. If we hadn't had this notation, things like[math]\frac{n!}{k!(n-k)!}[/math]would need to be replaced by unwieldy expressions like[math]\frac{\prod\limits_{i=1}^{n}i}{\prod\limits_{i=1}^{k}i\prod\limits_{i=1}^{n-k}i}[/math].Now you say, fine, it's just shorthand, but it's still a formula and not a program. But look at the expression we just wrote - what does it tell you to do? It tells you to follow certain instructions involving variables, memory, and loops. "Start with 1, multiply it with 2, multiply with 3, and keep going until you hit [math]n[/math]. Call this A. Now repeat with [math]k[/math] instead of [math]n[/math], and call that B, and then find C which has [math]n-k[/math] instead, and then divide A by the product of B and C, and that's your answer".That's an algorithm. It's written very compactly, but it's still an algorithm.The little expression "[math]n![/math]" is the result of applying an algorithm. Could be fast, could be slow, could be feasible on an iPhone, could be completely impossible to carry out (care to calculate it for [math]n=23^{23^{23}}[/math]?). It's an algorithm, a little computer program we happen to have a nice name for.It's the same with question 2. It's an algorithm. Multiply something by the result of adding those fractions in a loop. You've seen and accepted many such formulas without questioning them because you were told "here's a formula". But just consider what this actually means: to determine the expected number of coupons you will collect, you need to follow a recipe. Do a bunch of calculations. Just like so.All the formulas you've ever seen, including those with [math]\sum[/math] and [math]\prod[/math] and [math]\binom{n}{k}[/math] and stuff like that, all those formulas are neither more nor less than algorithms as in question 2, using standard notations that we've grown to accept as in question 1.(In fact, some formulas you may have seen aren't even algorithms - they are so complex they can't actually be calculated in any obvious way, or at all. But that's a different matter.)Now that we've established that, let's see - what is the difference between my answer to question 3, a formula for primes, and the answers to questions 1 and 2?There isn't any.When people say "there's no formula for prime numbers", what they actually mean is something very vague along the lines of "there isn't a short formula involving just a few of the symbols we learned in school". But that's not just vague, it's also demanding way more than is reasonable or meaningful to demand. So what if there's no such formula that uses just a few arbitrary shorthand symbols that we got used to for purely historical reasons? If we allow ourselves just a few more symbols we can simply write:[math]\displaystyle P(n) = \left\lfloor \frac{ n^2-\sum\limits_{d=2}^{n-1} \lfloor \frac{d-(n \% d)}{d} \rfloor }{ n^2} \right \rfloor [/math]and this is a formula for primality![math]P(n)=1[/math] precisely when [math]n[/math] is prime, and [math]0[/math] otherwise. You can turn this into a formula for the nth prime [math]p_n[/math] very easily:[math]\displaystyle p_n = \min \{ m< 2^n \,\mid\, \sum\limits_{k=2}^m P(k) = n\}[/math].Those are totally legit formulas for prime numbers. There's an official definition in math for "things that deserve to be called arithmetic formulas", and it is essentially the same thing as "anything you can write a computer program for".There are formulas for primes, the digits of the decimal expansion of [math]\pi[/math], and many other things. There are things we definitely don't have formulas for, either because we haven't been smart enough yet (e.g. the set of numbers which show up infinitely often as a difference of primes) or because such formulas are proven not to exist (e.g. the numbers which encode true arithmetical statements).That's a profound distinction, ripe with meaning and beauty and depth: the distinction between "computable", "possibly computable" and "most definitely not computable".But the distinction between "notationally very very simple formulas" and "formulas" isn't very profound or interesting, and it's the only sense in which "no formula for primes" is true. There's no tremendously primitive and restricted formula for primes. There are many, many formulas for primes which are just as straightforward to use as the answer to questions 1 and 2. Any computer program that produces primes is such a formula; you should be able to write one yourself in just a few lines of code.

I was playing around with several cubic representation problems in the style of previous work by Andrew and Richard Guy. The numerical results were fascinating…” (comment on MathOverflow)This is how Allan MacLeod, a retired mathematician, stumbled upon this equation just a few years ago, and it’s a really fascinating one. Honestly, it’s one of the finest diophantine equations I’ve seen, and I’ve seen a few.I came across it when it was making the rounds on the web as a nerd-sniping, faux-meme image designed by some cruel soul (Sridhar, was that you?). I had no idea what I was looking at. It looked like this:You may have seen such meme images before. They are always pure click-bait garbage: “95% of MIT graduates couldn’t solve this!”, where “this” is some inane, or ill-defined, or trivial brain teaser.This one is not. The meme is a clever, or wicked, joke. Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists. It is solvable, yes, but it's really, genuinely hard.(By the way, it wasn't actually Sridhar, or not exactly. See this comment for the history).You may think that, if all else fails, we can just throw computers at the problem. It’s really easy to write a computer program that searches for solutions of this simple-looking equation. Surely a computer will find them eventually, if they do exist. Wrong. A brute-force search with a computer is totally useless here.I don’t know how to fit the entire solution in a Quora answer without assuming that everyone already knows everything they need to know about elliptic curves. All I can do here is a brief survey. The main reference is a wonderful, and fairly recent, paper by Bremner and MacLeod called “An unusual cubic representation problem”, published in 2014 in the Annales Mathematicae et Informaticae.Let’s begin.We are looking for solutions in positive integers of the equation[math]\displaystyle \frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}=4 \tag 1[/math](I switched the variable names to match those in the paper).The first thing to do when you’re looking at any equation is to try and place it in the right context. What sort of thing is this? Well, we are being asked to find solutions in integers, so this is a problem in number theory. As it stands, the equation involves rational functions (polynomials divided by other polynomials), but it’s clear that we can multiply by a common multiple of the denominators to clear things up and get just polynomials, so we have a Diophantine equation. The “positive” requirement is somewhat unusual, and as we shall see it makes things harder.Now, how many variables do we have here? That seems like a silly question: clearly, we have three, namely [math]a[/math], [math]b[/math] and [math]c[/math]. Well, not so fast. A trained number theorist immediately notices that the equation is homogenous. What this means is that if [math](a,b,c)[/math] is any solution of that thing, then so is [math](7a,7b,7c)[/math]. Do you see why? Multiplying each variable by some constant number ([math]7[/math] is just an example) doesn’t change anything, because the constant cancels out in each of the fractions.[math]\displaystyle \frac{ta}{tb+tc}=\frac{ta}{t(b+c)}=\frac{a}{b+c}[/math].This means that the equation only pretends to be three-dimensional. It is actually two-dimensional. Geometrically, we have a surface (a single equation in three variables generically defines a two-dimensional surface. Generally, [math]k[/math] equations in [math]n[/math] variables define a [math]d[/math]-dimensional manifold, with [math]d=n-k[/math]). But this surface is actually swept by a line passing through the origin and waving about; the resulting surface can be understood by focusing on how it cuts a single plane. This is a projective curve.In the most elementary terms, this is what this reduction means: we can classify the solutions, whatever they are, to those where [math]c=0[/math] and those where [math]c\neq 0[/math]. The first class involves just the two variables [math]a[/math] and [math]b[/math], and for the second class we can just divide through by [math]c[/math] and get a solution with [math]c=1[/math]. So we can really just look for rational solutions in [math]a[/math] and [math]b[/math] for the case [math]c=1[/math], multiply them by a common denominator, and obtain an integer solution in [math]a,b[/math] and [math]c[/math]. Generally speaking, integer solutions of homogenous equations correspond to rational solutions of the dehomogenized version, which is one dimension lower.Next up: what is the degree of our equation? The degree is the highest power of any term showing up, where “term” is the product of some variables, whose “power” is then the number of terms being multiplied. For example, if you have [math]a^2bc^4[/math], that’s a term of degree [math]7=2+1+4[/math].Diophantine equations behave very differently depending on their degree. In broad terms:Degree [math]1[/math] is easyDegree [math]2[/math] is fully understood, and can usually be handled by relatively elementary meansDegree [math]3[/math] is a vast ocean of deep theory and a million open problemsDegree [math]4[/math] and up… Really, really hard.We are in degree [math]3[/math]. Why? Well, just multiply through by the denominators:[math]\displaystyle a(a+b)(a+c)+b(b+a)(b+c)+c(c+a)(c+b)=4(a+b)(a+c)(b+c)[/math]Even without explicitly expanding everything out, you can see how the degree is [math]3[/math]: we’re never multiplying more than three occurrences of any variable. We’re going to have things like [math]a^3[/math] and [math]b^2c[/math] and [math]abc[/math], but never anything that weighs more than [math]3[/math] units. If you carry out the actual rearrangement, you will find that the equation is[math]\displaystyle a^3+b^3+c^3-3(a^2b+ab^2+a^2c+ac^2+b^2c+bc^2)-5abc=0[/math].You may object that multiplying through by the denominators is illegal if any of them happens to be [math]0[/math]. This is true, and indeed our new equation has a few solutions that don’t correspond to anything in the original equation. But that’s actually a good thing. The polynomial version adds a few “patches” to the original and makes it easier to work with; for any particular solution we find, we just need to check that it doesn’t make any of the original denominators vanish.In fact, the polynomial equation is easily solved with, for instance, [math]a=-1[/math], [math]b=1[/math], [math]c=0[/math]. That’s good: we have a rational solution, or a rational point. This means that our cubic equation (degree-3) is actually an elliptic curve.When you find that your equation is an elliptic curve you A) rejoice and B) despair, because there’s so much to learn. This equation is a great example of how the powerful theory of elliptic curves can be applied to discover insanely hard to find solutions.The first thing you do with an elliptic curve is bring it to Weierstrass form. This is an equation that looks like[math]y^2 = x^3 + ax + b[/math]or sometimes[math]y^2 = x^3 + ax^2+bx+c[/math] (this is called the long Weierstrass form. It is not strictly needed, but sometimes it’s more convenient).It’s a basic fact that any elliptic curve can be brought to this form (except if you’re working over fields of small characteristic, which you needn’t worry about here). It’ll take me a whole big answer to explain how to find the right transformation. Just know that it’s a completely mechanical process (it relies, crucially, on the fact that we have at least one rational point, which we do). There are several computer algebra packages which will do this for you, easily.But even if you don’t know how to find the transformation, verifying it is easy – or, at least, purely mechanical. The required transformation in our case is given by the scary-looking formulas[math]\displaystyle x = \frac{-28(a+b+2c)}{6a+6b-c}[/math][math]\displaystyle y = \frac{364(a-b)}{6a+6b-c}[/math]I know this looks like random voodoo, but please believe me that it’s not. Once you have those transformations, a tedious but straightforward algebraic calculation confirms that[math]\displaystyle y^2 = x^3+109x^2+224x \tag 2[/math]This equation, though it looks very different, is actually a faithful model of the original. Graphically, it looks like this – a typical elliptic curve with two real components:The “fish tail” on the right keeps growing to infinity and beyond. The close oval shape on the left is, well, closed, and it will turn out that it’s where the fun is, for us.Given any solution [math](x,y)[/math] of this equation, you can recover the needed [math]a,b,c[/math] using[math]\displaystyle a = \frac{56-x+y}{56-14x}[/math][math]\displaystyle b = \frac{56-x-y}{56-14x}[/math][math]\displaystyle c = \frac{-28-6x}{28-7x}[/math](Remember that the triplet [math](a:b:c)[/math] is to be understood projectively – whatever values you get through those equations, you can always multiply them by whatever constant you wish).The two maps we exhibited, from [math]a,b,c[/math] to [math]x,y[/math] and vice versa, show that these two equations are “the same” from the perspective of number theory: rational solutions of one give you rational solutions of the other. The technical term is birational equivalence, and it’s a very fundamental concept in algebraic geometry. As we noted, there could be some exceptional points that don’t genuinely map correctly; those are the cases where [math]a+b, a+c[/math] or [math]b+c[/math] turn out to be [math]0[/math]. This is standard fare in birational equivalences, and shouldn’t cause any concern.Let’s look at an example.The elliptic curve (2) has a nice rational point on it: [math]x=-100[/math], [math]y=260[/math]. It’s not easy to find perhaps, but it’s super easy to verify: Just plug in those values and see that the two sides are the same (I didn’t choose this point at random, but never mind for now). We can simply check which [math]a,b,c[/math] values it yields. We get[math]a = 2/7, b=-1/14, c=11/14[/math]and since we can multiply by a common denominator, this can be modified into[math]a = 4, b=-1, c=11[/math].And indeed,[math]\displaystyle \frac{4}{-1+11}+\frac{-1}{4+11}+\frac{11}{4-1}=4[/math]as you can readily verify. This is a simple solution to our original equation in integers, but alas – not positive integers. This solution is not easy to see by hand, but it’s also not hard to discover with some patience without all the machinery we are reviewing here. It’s the positive solutions that are the lair of dragons.Now, as soon as you have a rational point on an elliptic curve, such as [math]P=(-100,260)[/math] on our curve (2), you can start generating others using the chord and tangent technique, which we covered on a previous Quora episode.To begin with, we can add our point [math]P[/math] to itself by finding the tangent to the curve at [math]P[/math], and seeing where it meets the curve again. The result turns out to be a bit scarier:[math]P+P=2P=(8836/25, -950716/125)[/math]and again, this new point corresponds to values of [math]a,b,c[/math] which solve our original equation:[math](a,b,c)=(9499, -8784, 5165)[/math].This solution is definitely not easy to find by hand, but it’s still manageable with a computer. However, it’s still not positive.Undeterred, we continue to calculate [math]3P=2P+P[/math] which is done by connecting [math]P[/math] and [math]2P[/math] with a straight line and finding its third point of intersection with the curve. And again, we calculate [math]a,b,c[/math], and again, the result isn’t positive. And so it is with [math]4P[/math], [math]5P[/math] and so on… until we hit [math]9P[/math].9P=(-66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921,  58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469) definitely not easy to find, but given our machinery, all we had to do was iterate a simple geometric procedure nine times. The corresponding values of [math]a,b,c[/math] are amazing:a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,  b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,  c=4373612677928697257861252602371390152816537558161613618621437993378423467772036 Those are [math]80[/math]-digit numbers! You cannot find [math]80[/math] digit numbers with a computer using brute force search. But unbelievable as it may seem, those huge numbers, when plugged into the simple expression [math]a/(b+c)+b/(a+c)+c/(a+b)[/math], yield exactly [math]4[/math].Those are, in fact, the smallest solutions to the problem. As we continue to add the point [math]P[/math] to itself, the denominators just keep growing. It is not quite easy to prove that, as there's always a possibility of some cancellation, but the theory of heights on an elliptic curve allows us to show that those astronomical numbers are, indeed, the simplest solutions to the question.Back to some theory. An elliptic curve over the rationals has a rank, which is the number of points we need to get started with the chord and tangent method and know that we will eventually find all rational points on the curve. Our specific elliptic curve (2) has rank 1, which means it has infinitely many rational points but they are all generated from a single one, which is none other than our point [math]P=(-100, 260)[/math]. The algorithms for calculating the rank and finding such a generator are far from trivial, but SageMath does it in under a second, using a few short lines of code. You can see my code here. It reconstructs the whole solution from scratch, but of course using Sage’s built-in methods for handling elliptic curves.In our case, the point [math]P[/math] lies on the oval part of the curve, and so do the points [math]mP[/math] for any positive odd integer [math]m[/math]. They sort of run around the oval and eventually cover it fairly uniformly. This is lucky, because only a small fraction of that oval yields positive solutions in terms of [math]a,b,c[/math]: it is the thickened portion in the following diagram, taken from Bremner and MacLeod’s paper.The points [math]P, 2P[/math] and so on don’t lie on the black part, but [math]9P[/math] does, which is how we got our 80-digit positive solutions.Bremner and MacLeod looked at what happens when we replace the [math]4[/math] with something else. If you think our solutions are big, wait till you see what happens when you try to represent [math]178[/math] in this way. Instead of 80 digits, you’ll need 398,605,460 digits. Yes, that’s just the number of digits in the solution. If you try [math]896[/math], you’ll be up to trillions of digits. Trillions. For this innocuous equation:[math]a/(b+c)+b/(a+c)+c/(a+b)=896[/math].This is a striking example of the way diophantine equations with tiny coefficients can have enormous solutions. This isn’t merely awe-inspiring, it is profound. The negative solution of Hilbert’s 10th problem means that the growth of the solutions as the coefficients get larger is an uncomputable function, for if it were computable, we would have had a simple algorithm for solving diophantine equations, and there isn’t one (simple or complex). Here, the correspondence [math]4 \to[/math] 80-digit numbers, [math]178 \to[/math] hundreds-of-millions-digit numbers and [math]896 \to[/math] trillions of digits gives us a glimpse into the first few tiny steps of that monstrous, uncomputable function. Tweak the numbers in your equation, and the solutions promptly exceed anything that fits in our puny little universe.What a wonderfully sneaky little equation.