132
$\begingroup$

The following popular mathematical parable is well known:

A father left 17 camels to his three sons and, according to the will, the eldest son should be given a half of all camels, the middle son the one-third part and the youngest son the one-ninth. This is hard to do, but a wise man helped the sons: he added his own camel, the oldest son took 18/2=9 camels, the second son took 18/3=6 camels, the third son 18/9=2 camels and the wise man took his own camel and went away.

I ask for applications of this method: when something is artificially added, somehow used and, after that, taken away (as was this 18th camel of a wise man).

Let me start with two examples from graph theory:

  1. We know Hall's lemma: if any $k=1,2,\dots$ men in a town like at least $k$ women in total, then all the men may get married so that each of them likes his wife. How to conclude the following generalized version?

    If any $k$ men like at least $k-s$ women in total, then all but $s$ men may get married.

    Proof. Add $s$ extra women (camel-women) liked by all men. Apply usual Hall lemma, after that say pardon to the husbands of extra women.

  2. This is due to Noga Alon, recently popularized by Gil Kalai. How to find a perfect matching in a bipartite $r$-regular multigraph? If $r$ is a power of 2, this is easy by induction. Indeed, there is an Eulerian cycle in every connected component. Taking edges alternatively we partition our graph onto two $r/2$-regular multigraphs. Moreover, we get a partition of edges onto $r$ perfect matchings. Now, if $r$ is not a power of 2, take large $N$ and write $2^N=rq+t$, $0<t<r$. Replace each edge of our multigraph onto $q$ edges, also add extra edges formed by arbitrary $t$ perfect matchings. This new multigraph may be partitioned onto $2^N$ perfect matchings, and if $N$ is large enough, some of them do not contain extra edges.

$\endgroup$
  • 10
    $\begingroup$ Maybe calculating the derivative of a function at a point could be considered as an example of this $\endgroup$ – Geoff Robinson Jun 7 '17 at 14:14
  • 18
    $\begingroup$ Well, you add a small increment to allow you to calculate a ratio which makes sense, then slowly decrease the increment until it disappears, but you are left a meaningful answer. Probably not the sort of thing you intended, but not an entirely unreasonable interpretation. $\endgroup$ – Geoff Robinson Jun 7 '17 at 14:29
  • 16
    $\begingroup$ No, the point was to realize that the division was by proportion, not by ratio, of the values (1/2,1/3,1/9). Remember the language in those days was differently expressive. Gerhard "And Not As Notationally Compact" Paseman, 2017.06.07. $\endgroup$ – Gerhard Paseman Jun 7 '17 at 16:20
  • 23
    $\begingroup$ Chemistry is the true home of this approach – every catalyst acts this way. $\endgroup$ – Gerry Myerson Jun 7 '17 at 23:45
  • 8
    $\begingroup$ I wonder if there's a classification of all sets of reciprocals where this can happen. Say, for which sets of integers $\alpha_i$ is there a solution to $(n+1)\sum \frac{1}{\alpha_i} = n$ with $\alpha_i | n+1$. $\endgroup$ – Aaron Bergman Jun 8 '17 at 0:50

45 Answers 45

61
$\begingroup$

Slack variables in linear programming. Quote from the link:

In an optimization problem, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint.
$\endgroup$
  • 12
    $\begingroup$ In the same spirit, in order to show that $GL_n$ is an algebraic group, one introduces the new variable $y$ and then takes the quotient by $y\cdot\det(x_{ij})=1$. $\endgroup$ – Andrei Smolensky Jun 7 '17 at 15:24
  • $\begingroup$ @AndreiSmolensky, surely the usual approach is to consider the subgroup where $y\cdot\det(x_{i j}) = 1$? I guess it depends on whether you are looking at the algebra $k[\mathrm{GL}_n] = k[x_{ij}, y]/(y\cdot\det(x_{i j}) = 1)$ or the group $\mathrm{GL}_n = \{(x_{i j}, y) \in \mathbb A^{n^2 + 1} : y\cdot\det(x_{i j}) = 1\}$. $\endgroup$ – LSpice Jun 7 '17 at 21:56
  • $\begingroup$ @LSpice For some people it is usual to use the scheme approach. Anyway, both options serve equally good for the original question. $\endgroup$ – Andrei Smolensky Jun 7 '17 at 22:05
  • 1
    $\begingroup$ Articifical variables, added to determine whether a linear program has a feasible solution, then taken away when the feasible solution is found (and all the artificial variables have a value of zero) is a better analogue. $\endgroup$ – mob Jun 12 '17 at 23:23
52
$\begingroup$

Lagrange multipliers: to extremize $f(x,y)$ subject to constraint $g(x,y)=0$, add a variable $\lambda$ and

introduce an auxiliary function $$ {\mathcal {L}}(x,y,\lambda )=f(x,y)-\lambda \cdot g(x,y) $$ and solve [unconstrained!] $$ \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0. $$ Note that this amounts to solving three equations in three unknowns. This is the method of Lagrange multipliers. Note that $\nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0$ implies $g(x, y) = 0$. To summarize $$ {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\iff {\begin{cases}\nabla _{x,y}f(x,y)=\lambda \nabla _{x,y}g(x,y)\\g(x,y)=0.\end{cases}}} $$

$\endgroup$
48
$\begingroup$

The AM-GM inequality (as well as other inequalities, for instance the discrete version of Jensen's inequality) can be proved with the following trick due to Cauchy, known as "forward-backward induction":

Let $P(n)$ be the proposition "For any $n$ positive reals, $\frac1n \sum a_i \geq (\prod a_i)^{1/n}$" (AM-GM inequality with $n$ terms).

The proof is made of three parts.

  1. Prove $P(2)$ directly.
  2. Use $P(n)$ and $P(2)$ to prove $P(2n)$ (hence by induction we can now prove $P(2^k)$ for each $k$).
  3. Given $n$ terms $a_1,a_2,\dots, a_{n}$, use $P(n+1)$ on the $n+1$ terms $a_1,a_2,\dots, a_n, \frac1n \sum a_i$ to derive $P(n)$ with a few manipulations.

So when we want to prove $P(n)$ for a generic $n$, we use part 3 to add several "phantom" terms equal to $AM=\frac1n \sum a_i$ to make $n$ a power of 2, then use parts 1+2.

The proof is described in more detail here.

$\endgroup$
  • $\begingroup$ The most classic! $\endgroup$ – yo' Jun 7 '17 at 20:17
47
$\begingroup$

The usual way to prove the Strong Nullstellensatz from the Weak Nullstellensatz is the so-called Rabinowitsch trick.

In short, adding an extra variable allows us to apply the "weak" version of the theorem; then we can come back to the smaller polynomial ring and get the "strong" version by simply clearing denominators.

See also this MO question.

$\endgroup$
43
$\begingroup$

Maybe this example is too elementary for this site, but I'd say the proof that a closed subset of a compact set is compact itself looks like this. Given an open cover of a $A$ where $A$ is a closed subset of a compact set $K$ we add $K\setminus A$ to the cover, obtain a finite subcover using compactness of $K$ and then discard the extra set as it is not needed to cover $A$.

$\endgroup$
29
$\begingroup$

Another example of this could be a proof by induction where we add additional constraints to our induction hypothesis to prove something stronger. For example,

Show that $\sum_{k = 1}^{n} \frac{1}{k^2} < 2$

cannot be proved by induction, but we can add in a tiny modification and prove the following instead:

Show that $\sum_{k = 1}^{n} \frac{1}{k^2} < 2 - \frac{1}n.$

We can then 'take away' the $\frac{1}n$ to return to our original statement.

$\endgroup$
  • 3
    $\begingroup$ Statements of the form "cannot be proved by induction" are surely dangerous (and, indeed, you outline a counterexample). Maybe better to say "[this statement] cannot be directly proved by induction", or "it's not obvious how to prove [this statement] by induction"? $\endgroup$ – LSpice Nov 27 '17 at 1:11
27
$\begingroup$

The general formula for solving second degree equations. You need to add a term to complete the square and then subtract a little more to take the square root.

$\endgroup$
23
$\begingroup$

A common task in digital signal processing is to compute the convolution of two functions over $\{0,\ldots,n-1\}$. The standard approach is to first "pad with zeros" by viewing these as functions over $\mathbb{Z}/2^k\mathbb{Z}$ with $2^k\geq 2n$. Then it suffices to compute the circular convolution, which can be obtained in $O(n\log n)$ time via the Cooley–Tukey fast Fourier transform.

This is also the main trick under the hood of the Schönhage–Strassen algorithm for fast integer multiplication.

$\endgroup$
23
$\begingroup$

Since nobody did, I would like to mention the obvious: The 17 camels trick is routinely used in apportionment procedures called divisor methods.

The task is to divide a number of $N\in\mathbb N$ items (e.g., seats in a parliament) according to fixed proportions $p_1,\ldots,p_n>0$ (e.g., results of an election). One way to do this is to define a rounding procedure $\mathbb R\to\mathbb Z:x\mapsto[x]$. The idea is to add additional $\epsilon\in\mathbb R$ virtual seats and tweak it such that the contingents $N_i:=[p_i(N+\epsilon)]$ sum up to $N$. This is almost always possible and the $N_i$ are unique in this case.

The different divisor methods differ by the rounding method: If $[x]$ is

  • rounding down: Jefferson's (aka d'Hondt) method
  • rounding up: Adam's method
  • rounding at the arithmetic mean: Webster/Sainte-Laguë method
  • rounding at the geometric mean: Huntington–Hill method (currently used for the US-House of Representatives)
$\endgroup$
  • 2
    $\begingroup$ This just makes me think of sketchy american politics and makes me ansty. Lol. $\endgroup$ – user78249 Jun 9 '17 at 23:33
  • $\begingroup$ by the way, in initial problem $\varepsilon=0$: 17 camels (or seats, if you like) are perfectly divided in the proportion of 1/2:1/3:1/9 $\endgroup$ – Fedor Petrov Jun 14 '17 at 10:01
19
$\begingroup$

In many cases, an integral over the reals can be conveniently evaluated with the help of contour integration in the complex plane.

$\endgroup$
16
$\begingroup$

This method is rather common when considering topological invariants. We often add structure to define some quantity, then later show that the quantity is independent of the choice we made.

A simple example is the computation of the Euler characteristic of a surface. We typically choose a triangulation, then compute #vertices - #edges + #triangles. More recent constructions like singular homology allow us to define Euler characteristic without adding a camel choosing a triangulation, but the computation with triangulations is concrete and relatively quick.

More complicated examples abound, where the camel may take the form of a Riemannian metric, a Morse function, a projection of a link to a plane, etc.

$\endgroup$
16
$\begingroup$

Evaluation of definite integrals via the method of differentiation under the integral sign has this character. This probably needs no introduction, but the idea is to view the integrand $f(x)$ of $\int_a^b f(x)\; dx$ as belonging to a (judiciously chosen) parametrized family of functions $F(x, t)$, say at $t = t_0$. (So the parameter $t$ is the 18th camel.) Under mild hypotheses the function

$$G(t) = \int_a^b F(x, t)\; dx$$

has derivative

$$G'(t) = \int_a^b \frac{\partial}{\partial t} F(x, t)\; dx$$

and in many cases this will be simple enough to allow one to solve for $G(t)$. Then the original integral is $G(t_0)$. The Wikipedia article gives some examples of this technique (made popular by Feynman through his book "Surely You're Joking, Mr. Feynman!").

My impression is that the method of creative telescoping is similar in nature; perhaps others more knowledgeable about this can weigh in.

$\endgroup$
  • $\begingroup$ I'm not sure how creative telescoping applies here. For me, I always thought creative telescoping was finding $\Delta y = F(x)$ when the solution $y$ requires a non-obvious approach. I could be wrong though. +1 for Feynman's method though, I use it all the time and sometimes I lost marks because "I didn't use contour integration." $\endgroup$ – user78249 Jun 9 '17 at 23:30
  • 1
    $\begingroup$ @james See here specfun.inria.fr/chyzak/Publications/Chyzak-2012-CTP.pdf, p. 4 ff. In fact, we "discussed" this once before! See my comment under your post here: mathoverflow.net/a/263508/2926 $\endgroup$ – Todd Trimble Jun 9 '17 at 23:57
  • $\begingroup$ I was very mistaken by what I thought creative telescoping is. It's much more subtle, and does sound a lot like the 17 camels trick. My mistake :). I also do remember our little conversation about Feynman. $\endgroup$ – user78249 Jun 10 '17 at 0:04
  • $\begingroup$ This answer would also fit here: mathoverflow.net/questions/74214/… $\endgroup$ – Somatic Custard Oct 19 '17 at 12:55
14
$\begingroup$

A nice example is Parking Functions. This is a well-known topic in combinatorics with connections ranging from spanning trees of graphs to non-crossing partitions to hyperplane arrangements to priority queues.
Our wise man will realize that the ostensibly linear setting I describe below would be significantly easier to handle if he lent us a placeholder camel which could offer us cyclic symmetry. This camel-on-loan will provide the structure to do a trivial calculation, and in the end, we can simply pluck out all the solutions that didn't involve it, discarding the rest.

(Although I could be cheeky and state the entire problem in terms of camels, I'll try to resist and be faithful to the normal presentation).

Imagine a shopping plaza with $n$ parking spaces laid out linearly in front of the stores. In the morning, $n$ shoppers $s_i$ file into the plaza one at a time ($s_1$ arrives, then $s_2$, then $s_3$, etc.) each one having a strong preference for parking space $p_i$ in front of the store they are visiting.

The problem is that the parking lot is narrow — the flow of traffic is one way — and the shoppers are rather shortsighted and obstinate: shopper $s_i$ drives up to their preferred space $p_i$, and if they find it occupied, they keep going to the first available $p$ such that $p > p_i$; if no such $p$ exists, they get frustrated and shop elsewhere.

The situation for n = 12 is shown below. Supposing the next four shoppers $s_7$ thru $s_{10}$ were all both planning to park at space $8$ and get breakfast at Subway, they'll land at the $8$th, $10$th, and $11$th spots respectively, and the $10$th shopper will find a sandwich elsewhere. enter image description here

We can encode the preferences of the shoppers with an $n$-tuple $(p_1, p_2, \ldots, p_n)$. Now we denote by $P(n)$ the set of $n$-tuples encoding situations in which all $n$ shoppers will find a place to park — the parking functions of length $n$.

To calculate the size of $P(n)$, you can scratch your head for a while thinking about the problem linearly, or you can exercise an "add one subtract one" trick — let's take the old wise man up on his offer and throw a camel into the mix:

Consider adding another space $n+1$ to the parking lot which "glues" together the two ends (so now shoppers that can't park in their preferred spot will go around in a circle til they find a place). That means that in our new arrangement, everyone can always park! Moreover, there's always one space left empty. Preferences for this augmented lot are encoded as $n$-tuples taking values as residue classes modulo $n+1$, so there are $(n+1)^n$ of them. The placement of the single unoccupied parking space is equidistributed, so $(n+1)^{n-1}$ preference tuples leave the $n+1$ spot vacant. We lastly verify that each of these preference tuples leaving the $n+1$ spot vacant, when taken at face-value, is a parking function:

Suppose you considered a parking function as encoding preferences for the augmented circular lot. Since it was a parking function, the shoppers don't need to loop around in order to park, and the resultant arrangement leaves the $n+1$ space empty. Conversely, a preference tuple on the augmented lot that results in the $n+1$ space unoccupied was such that no shopper had a preference for the $n+1$ space, and no shopper ever did a loop around the lot (since they park as soon as possible), hence it's a parking function.

Thus we find $P(n) = (n+1)^{n-1}$ by thinking about an extra space gluing the ends of the parking lot together, and then showing that all the ways of avoiding that extra structure are the very objects we are enumerating.

Actually if I squint hard enough this almost seems vaguely reminiscent of the general methodology of proving something about a topological space $X$ by porting a result on some compactification of $X.$

$\endgroup$
  • 2
    $\begingroup$ This is beautiful. $\endgroup$ – benblumsmith Jun 14 '17 at 4:39
  • $\begingroup$ I'm glad you did not word this in terms of camels. Parking cars in camels would be a rather counterintuitive metaphor! $\endgroup$ – darij grinberg Jul 1 '17 at 23:11
  • 2
    $\begingroup$ one could consider parking camels instead of cars. $\endgroup$ – yael fregier Feb 27 '18 at 12:27
  • $\begingroup$ I didn't understand why "Preferences for this augmented lot are encoded as n-tuples taking values as residue classes modulo n+1" and why "The placement of the single unoccupied parking space is equidistributed". $\endgroup$ – Michael Feb 26 at 23:51
12
$\begingroup$

I think a fun example of this is the simplification of $$\sum_{k=1}^n \sin kx.$$ First multiply by $\sin \frac x2$ to get $$\sum_{k=1}^n \sin kx \sin \frac x2 = \sum_{k=1}^n \frac 12 \left[ \cos (k - \frac 12)x - \cos(k + \frac 12)x \right] = \frac{\cos \frac x2 - \cos(n + \frac 12)x}2$$ then divide by the same term to find $$\sum_{k=1}^n \sin kx = \frac{\cos \frac x2 - \cos(n + \frac 12)x}{2\sin \frac x2}.$$

$\endgroup$
  • 6
    $\begingroup$ We could start with the summation of geometric progression $1+x+\dots+x^{n-1}$ via multyplying it by $1-x$. $\endgroup$ – Fedor Petrov Jun 12 '17 at 12:08
11
$\begingroup$

This does not quite match your criteria, but feels similar. It is a method for multiplying two decimals, say $13 \times 27$. Form two columns headed by $13$ and $27$. Halve $13$ and discard any remainder, and double $27$. Continue halving the first column and doubling the second until the first column reaches $1$:

\begin{array} \mbox{13} & 27 \\ {\color{red}{6}} & {\color{red}{54}} \\ 3 & 108 \\ 1 & 216 \end{array}

Now discard any row for which the first column is even ($\color{red}{6}$ above). Sum the remaining elements of the second column: $$27 + 108 + 216 = 351 = 13 \times 27 \;.$$ This is of course using the binary representation $13 = 2^0 + 2^2 + 2^3$, and first including but later excluding the $2^1$ row $\color{red}{6} \;\; \color{red}{54}$.

$\endgroup$
  • $\begingroup$ I think something is missing from this explanation, as the method doesn't seem to work quite reliably. 11x42 comes out as 84+336=420, which is not correct $\endgroup$ – davidcl Jun 7 '17 at 21:06
  • 3
    $\begingroup$ @davidcl: $11 \; 42$, $5 \; 84$, $2 \; 168$, $1 \; 336$, and then $42 + 84 + 336 = 462 = 11 \times 42$. $\endgroup$ – Joseph O'Rourke Jun 7 '17 at 21:43
11
$\begingroup$

enter image description here

The ancient proof of the Pythagorean Theorem: add four triangles to $c^2$ and remove them to get $a^2+b^2$.

$\endgroup$
10
$\begingroup$

The replica trick/method in statistical physics (and more recently machine learning) computes a property of a system by considering $n$ copies of the system and then taking a limit $n \downarrow 0$.

$\endgroup$
10
$\begingroup$

This seems like a good place to advertise LSpice's great answer (spread out over a series of comments) to my earlier MO question Where does the really nice '8-dimensional' description of the $E_7$ root system come from?, where LSpice shows that $E_8$ has a $E_7 \times A_1$ subalgebra by adding and removing one node to/from the Dynkin diagram.

$\endgroup$
  • 1
    $\begingroup$ Wow, thanks! For what it's worth, this is by no means original to me; it is the Borel–de Siebenthal classification of the maximal-rank reductive subgroups of a reductive group. $\endgroup$ – LSpice Nov 27 '17 at 1:15
10
$\begingroup$

One instance I am very fond of:

If $m,n$ are positive integers and $n$ is odd, then $S^m\times S^n$ has trivial tangent bundle.

Proof. Here the wise man is the tangent bundle of $S^n$. Think $T(S^m\times S^n)=TS^m\oplus TS^n$. Since $n$ is odd, $S^n$ has a nowhere vanishing vector field, so up to isomorphism $TS^n$ splits as $\mathbb{R}\oplus F$, where $\mathbb{R}$ denotes the trivial one-dimensional vector bundle.

Now the wise man $TS^n$ lends the trivial piece $\mathbb{R}$ to $TS^m$ and $TS^m\oplus\mathbb{R}$ becomes trivial, since (the pullback by $S^m\hookrightarrow\mathbb{R}^{m+1}$ of) $T\mathbb{R}^{m+1}$ equals $TS^m\oplus\mathbb{R}$, due to the presence of the outward unit normal.

So $TS^m\oplus\mathbb{R}=\mathbb{R}^{m+1}$ and now the wise man takes (a copy of) his $\mathbb{R}$ back to form again $TS^n$. Finally, he takes another $\mathbb{R}$ to trivialize himself in the same way.

$\endgroup$
9
$\begingroup$

I just want to precise what really happened in the story, in case some are left wondering:

There was no way to partition the 17 camels as described, without having non-integer parts of camels... To (wisely) avoid that, the wise man changed the partitionning a bit (in the end, each son got a different amount of camels than they should have had, but they all got live camels, which is a win). The wise man made sure that he added whatever camels were needed to ensure a integer division among the sons, and took those back in the end.

Ie, the sons never received "1/2" "1/3" and "1/9" of 17 camels, but instead received the 1/2th, 1/3th and 1/9th of 18 camels, which amounted to only 17 camels (as 1/2, 1/3 and 1/9 is equal to 9/18+6/18+2/18 = 17/18. The wise man just represented the remaining 1/18th part with his camel.)

$\endgroup$
  • 37
    $\begingroup$ To put it another way, every son did get what he was promised, but there was 17/18 of a camel that wasn't promised to anybody. The wise man's solution provided a convenient way to share out that 17/18 of a camel in addition to the promised shares, such that everyone wound up with integer camels. If the will had gone on to say "I leave all remaining property to my wife", then she would be shorted to the tune of 17/18 of a camel by this scheme, so you could expect to see her in court. $\endgroup$ – Nate Eldredge Jun 7 '17 at 20:23
8
$\begingroup$

A very simple application of this technique is a mental math strategy: round to a number that's easy to work with, then reverse the rounding later.

? = 56 + 17

? = 60 + 17 - 4

? = 77 - 4

? = 73

You have to be a bit more careful with multiplication and division, but it works just the same.

? = 43.25 * 15%

? = 43.25 * 10% + 43.25 * 5%

? = 4.32 + 43.25 * 10% / 2

? = 4.32 + 4.32 / 2

? = 4.32 + 2.16

? = 6.48

$\endgroup$
8
$\begingroup$

To learn a good classifier, you want a large training set of labeled data. In many settings, data is cheap but labels are expensive, requiring human labor. So what do we do with a bunch of unlabeled data?

Sometimes, the unlabeled data will reveal helpful clusterings:

enter image description here

Incorporating unlabeled data in the classification task is called semi-supervised learning, and this has found success recently in various state-of-the-art classifiers based on deep learning.

$\endgroup$
8
$\begingroup$

The Catalan number $C_n= \frac{2n \choose n}{n+1}$ counts the number of binary strings with $n$ $1$s and $n$ $0$s so that every prefix has at least as many $1$s as $0$s. There is a combinatorial proof, I think due to Cauchy, which involves an 18th camel.

There are $2n \choose n$ binary strings with $n$ of each letter. Add an $n+1$st $1$ to the end of each word! There are $n+1$ cyclic rotations ending in $1$. Precisely one of these has the property that each prefix has at least as many $1$s as $0$s. (This is nontrivial but not hard to prove.)

For example, the $5$ rotations of $11100010$ are

$$\begin{eqnarray}11100010{\color{red}1} \newline 11000101{\color{red}1} \newline 10001011{\color{red}1} \newline 00010111{\color{red}1}\newline 01111000{\color{red}1}\end{eqnarray}$$

with the 18th camels in red.

$\endgroup$
  • $\begingroup$ Cauchy, really? I'm intrigued... $\endgroup$ – Todd Trimble Oct 11 '17 at 0:09
  • $\begingroup$ @Todd Trimble: It sounded reasonable to me when I heard it. However, I haven't found a reference. $\endgroup$ – Douglas Zare Oct 11 '17 at 8:57
  • $\begingroup$ According to Wikipedia, this is due to Dvoretzky and Motzkin from 1947. $\endgroup$ – Jarek Kuben Nov 13 '17 at 14:56
7
$\begingroup$

When proving that a finite flat simple group scheme $G$ of $2$-power order over $\mathrm{Spec}\,\mathbf{Z}$ is of order $2$ (and hence isomorphic to $\mu_2$ or $\mathbf{Z}/2$), one proves that for $K = \mathbf{Q}(G(\bar{\mathbf{Q}}))$ the Galois group $\mathrm{Gal}(K/\mathbf{Q})$ is a $2$-group.

In order to prove this, one enlarges $G$ to $\tilde{G} := G \times G_{-1}$ with the Katz-Mazur group scheme $G_{-1}$ sitting in an exact sequence $1 \to \mu_2 \to G_{-1} \to \mathbf{Z}/2 \to 0$. Then one proves that $\mathbf{Q}(G_{-1}(\bar{\mathbf{Q}})) = \mathbf{Q}(i)$, and by the Odlyzko bounds (this uses that $\tilde{K} := \mathbf{Q}(\tilde{G}(\bar{\mathbf{Q}}))$ is totally imaginary since $\mathbf{Q}(i)$ is), one has $[\tilde{K}:\mathbf{Q}] \leq 4$, so since one has the inclusions of fields $\tilde{K} \supseteq \mathbf{Q}(i) \supseteq \mathbf{Q}$, $\mathrm{Gal}(\tilde{K}/\mathbf{Q})$ is a $2$-group, hence so is $\mathrm{Gal}(K/\mathbf{Q})$.

So the trick is to add $G_{-1}$.

This is used in proving Fontaine's theorem that there is no non-trivial Abelian scheme over $\mathrm{Spec}\,\mathbf{Z}$. See the notes of René Schoof https://math.dartmouth.edu/~jvoight/notes/274-Schoof.pdf, p. 41–43.

$\endgroup$
7
$\begingroup$

In physics, the canonical example is the case of gauge theories. There are different levels of sophistication:

  • Classical electromagnetism: here the "physical" variables are the components of the two form $F$ (the electromagnetic field). In principle, one may formulate the theory purely in terms of $F$, with no extra camels. On the other hand, the general analysis greatly simplifies if one introduces extra variables in the form of a one form $A$, such that $F=\mathrm dA$. As usual, the differential form $A$ is defined up to an arbitrary exact form. General field configurations (the solutions of the equations of motion), when written in terms of $A$, depend on one arbitrary function, reflecting the presence of extra "unphysical" degrees of freedom.

  • Classical Yang-Mills: here we have several two-forms $F$ (living in the adjoint representation of a certain Lie Group) such that $F=\mathrm dA+A\wedge A$. Here, and unlike before, it is impossible to formulate the theory purely in terms of $F$, and therefore one is forced to introduce the one forms $A$. As before, these are not uniquely determined given $F$, and therefore general field configurations depend on several arbitrary functions.

  • Quantum Yang-Mills: in order to have a manageable and consistent theory, one is obliged to introduce more "unphysical variables", i.e., more extra fields. These are the so-called Faddeev-Popov ghosts, and they greatly simplify the general formalism but, once again, they are auxiliary, unobservable fields. They do not affect measurable predictions.

  • Other quantum gauge theories: the most general and systematic approach to the quantisation of gauge theories that we know of as of today is the Batalin-Vilkovisky formalism. In this formalism, one introduces one auxiliary variable for each field that one is working with. That is, the first step towards the quantisation of the theory is to duplicate the number of variables (which include the gauge fields themselves, as well as any Faddeev-Popov ghost, or any other auxiliary field that is present). These variables are eventually eliminated, but their presence greatly simplifies the general analysis.


Other examples in physics:

  • Stückelberg fields, which are extra fields that are introduced to maintain gauge invariance in massive theories. In the same vein, the Goldstone-like components of the Higgs field.

  • Pauli-Villars fields, which are introduced to ensure convergence of certain integrals. They are eventually eliminated (after making sure that there are no measurable divergences).

  • Inonu-Wigner contraction: sometimes, one may understand a certain group as the contraction of a larger group. If the larger group is simpler than the contracted one, one may use this information to simplify the analysis of the contracted group. Such is the case of the Poincaré Group, which is the contraction of $\mathrm{SO}(4,1)$ (the latter being semi-simple, and the former not). The explicit contraction allows us to obtain, for example, the rank and Casimirs of Poincaré in terms of those of $\mathrm{SO}(4,1)$.

  • The method of image charges, which is a strategy to solve certain problems in electrostatics by introducing extra "fictitious" point-charges, and exploiting the symmetry of the resulting configuration. One should note that this technique can be used to obtain certain Green functions provided the domain is simple enough.


Finally, I'm surprised no one has mentioned the standard trick to calculate the Gaussian integral $$ \int\mathrm e^{-x^2}\mathrm dx=\sqrt{\pi} $$ by introducing a second coordinate $y$, such that $$ \left(\int\mathrm e^{-x^2}\mathrm dx\right)^2=\int\mathrm e^{-r^2}\mathrm dx\,\mathrm dy $$ and changing to polar coordinates.

$\endgroup$
  • $\begingroup$ Also: embedding a manifold in a larger one in order to simplify its analysis. Off the top of my head, I can't think of any explicit example though. $\endgroup$ – AccidentalFourierTransform Jun 12 '17 at 13:59
6
$\begingroup$

The spoiler effect in voting theory concerns how a "spoiler candidate" with ideology similar one major candidate can split the vote in favor of another major candidate. This effect is a common criticism of the IIA axiom, and enjoys a history of application in real-world democracy.

$\endgroup$
5
$\begingroup$

Grobner basis methods for testing subalgebra membership are another example. You add extra variables in order to take advantage of the good features of Grobner bases for elimination orders. You can throw them out afterward.

For example: say you want to find out whether a given polynomial $f\in k[x_1,\dots,x_n]$ is in the subalgebra generated by a specific set $g_1,\dots,g_\ell \in k[x_1,\dots,x_n]$ of other polynomials, and if it is, to find a representation of $f$ in terms of the $g_i$'s. Create a new polynomial ring with new indeterminates $G_1,\dots,G_\ell$ and $F$:

$$R = k[x_1,\dots,x_n,F,G_1,\dots,G_\ell]$$

Now compute a Grobner basis for the ideal

$$(g_1-G_1,\dots,g_\ell-G_\ell,f-F)$$

with respect to an elimination order in which $x_i > F > G_j$ for all $i,j$. If $f$ is a polynomial in the $g$'s, then there will be a corresponding element in the Grobner basis with the form

$$F-\text{polynomial in the }G\text{'s},$$

indicating the representation of $f$ in terms of $g$'s. If not, there will be no such element in the Grobner basis.

$\endgroup$
4
$\begingroup$

Suppose that we need to divide 9 people into two volleyball teams. Usually we start with two captains (best players). First captain choose one player. After that second captain and first captain choose two players on each step. The problem is in bad players which may have negative weight in the team. And in the end of this procedure captains obliged to choose bad players.

This algorithm will work better if we'll complete the original group with 3 (3+9=12) virtual (empty) players (with zero weight). So each captain may take one of the empty player instead of negative ones.

$\endgroup$
  • $\begingroup$ Sorry, how to divide 9 people into two volleyball teams? I am confused. $\endgroup$ – Fedor Petrov Jun 8 '17 at 8:41
  • 2
    $\begingroup$ There are 9 people who want to play volleyball. And we need to divide them somehow. $\endgroup$ – Alexey Ustinov Jun 8 '17 at 8:47
  • $\begingroup$ ok, but we can not divide them by 6+6, right? So, should we divide by 5+4 or not necessarily? $\endgroup$ – Fedor Petrov Jun 8 '17 at 8:53
  • $\begingroup$ I think the point is that each player has a weight and you want the distribution of weight to be as fair as possible - so it is not necessary that the division is 4-5... $\endgroup$ – Asvin Jun 9 '17 at 12:06
  • $\begingroup$ Yes, 4+5 is not necessary. One captain may take 3 empty players and they will get 3+6. $\endgroup$ – Alexey Ustinov Jun 9 '17 at 12:17
4
$\begingroup$

When learning the derivative and its various rules, the intuitive undergrad way of proving the product formula kind of does this. We add an $f(x+h)g(x) - f(x+h)g(x)$ and the product formula just pops out. Of course I've never seen this proof rigorously done. I've just seen it used as an ad hoc way to convince people not fluent in epsilon-delta.

$\endgroup$
  • 1
    $\begingroup$ What's not rigorous about this? $\endgroup$ – LSpice Nov 27 '17 at 1:11
4
$\begingroup$

In model theory, you often add different symbols to the language you're interested in, to prove a result and then go back to the original language to have the theorem you wanted.

To be more precise, here's an example : suppose you want to show that a theory $T$ in a language $L$ with arbitrarily large finite models has infinite models of arbitrarily large cardinality.

You pick a cardinal $\kappa$, add $\kappa$-many new symbols $c_\alpha$ for $\alpha<\kappa$ to the language $L$ to get $L'$. Then you notice that $T\cup\{c_\alpha\neq c_\beta \mid \alpha\neq \beta \in \kappa\}$ is finitely consistent by hypothesis; and so by compactness it is consistent.

Take a model $M$ of $T'$ and consider its $L$-reduct $\tilde{M}$. This is a model of $T$ and it has cardinality $\geq \kappa$ : we added stuff to $L$ to get what we wanted, then removed it to have a theorem about $L$.

$\endgroup$

protected by Asaf Karagila Jun 17 '17 at 8:36

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.