text:
# CLEP College Algebra/Exponents

Imagine there was a natural number ${\displaystyle a}$ that was added to itself repeatedly over ${\displaystyle b}$ times. The integer ${\displaystyle a}$ is called the multiplicand (the thing being multiplied) while ${\displaystyle b}$ is the multiplier (the thing you are multiplying to the multiplicand). The result of this operation is the product. We refer to this specialized operation, ${\displaystyle P(a,b)}$, as multiplication, which is one of the definitions of multiplication:

${\displaystyle P(a,b)=\underbrace {a+a+a+\cdots +a+a+a} _{b}{\overset {\underset {\mathrm {def} }{}}{=}}a\cdot b=a\times b=a(b)=ab}$

This idea does not seem to work for integers. Let ${\displaystyle b\in \mathbb {Z} ^{-}}$ and ${\displaystyle a\in \mathbb {Z} ^{+}}$ be a part of, henceforth referred to, multiplication function ${\displaystyle P(a,b)}$. If ${\displaystyle P(a,b)=\underbrace {a+a+a+\cdots +a+a+a} _{b}{\overset {\underset {\mathrm {def} }{}}{=}}ab}$, then how can a number be added to itself negative times?

This dilemma requires us to work through a special case of ${\displaystyle b\in \mathbb {Z} ^{+}}$ and ${\displaystyle a\in \mathbb {Z} ^{-}}$. Let us say the following is true: ${\displaystyle a=-p}$ and ${\displaystyle b=q}$ whereby ${\displaystyle p\in \mathbb {Z} ^{+}}$ and ${\displaystyle q\in \mathbb {Z} ^{+}}$. Let us go ahead and input these two variables into our multiplication function:

${\displaystyle P(a,b)=\underbrace {a+a+a+\cdots +a+a+a} _{b}=\underbrace {(-p)+(-p)+(-p)+\cdots +(-p)+(-p)+(-p)} _{q}{\overset {\underset {\mathrm {def} }{}}{=}}-pq}$

The above definition tells us to simply subtract ${\displaystyle a}$ from itself ${\displaystyle b}$ times for ${\displaystyle a\in \mathbb {Z} ^{-}}$ while ${\displaystyle b\in \mathbb {Z} ^{+}}$. There is no problem since the number ${\displaystyle a}$ is subtracted ${\displaystyle b}$ times, despite it being negative. This is one of the ways we can say a negative times a positive number is negative (over the set of integers). However, this definition breaks down once we switch the roles of the number. Our next example shall attempt to prove a basic "theorem" most of us already know.

 Proof 1: Prove that multiplying ${\displaystyle a\in \mathbb {Z} ^{+}}$ to ${\displaystyle b\in \mathbb {Z} ^{-}}$, or ${\displaystyle x(-y)}$ for ${\displaystyle a=x}$ and ${\displaystyle b=y}$ given ${\displaystyle x\in \mathbb {Z} ^{+}}$ and ${\displaystyle y\in \mathbb {Z} ^{+}}$, is equivalent to ${\displaystyle -xy}$. First, we need to define what it means for a number to be negative. This is important to establish formally before we use it in our proof. Recall that one property of being a negative number is that it is the additive inverse of the magnitude of the number. That is, given a number ${\displaystyle x\in \mathbb {Z} ^{+}}$, the additive inverse is ${\displaystyle -x}$. Also, a number must equal itself; this is by definition true. This is the property of equality, and it is important in establishing our theorem. Let us say we are trying to solve the problem ${\displaystyle x(-y)+xy}$. By the property of equality, (2.0.0.1) ${\displaystyle x(-y)+xy=x(-y)+xy}$ In (2.0.0.1), notice how ${\displaystyle x}$ is a factor of both terms on the right hand side. This means that we may rewrite the equation as the following: (2.0.0.2) ${\displaystyle x(-y)+xy=x(-y+y)}$ Recall that we defined the negative number to be the inverse operation. By the additive inverse property, ${\displaystyle -y+y=0}$. Therefore, we know ${\displaystyle x(-y+y)=x(0)=0}$. We know any number times zero equals zero since we proved this was true in the previous chapter. Ergo, we have a new property: (2.0.0.3) ${\displaystyle x(-y)+xy=0}$ By an extension of the property of equality, whatever is done to one side of an equation requires it must be done to the other. From this property of integers, we may define simply this: (2.0.0.4) ${\displaystyle x(-y)=-xy}$ From this, we have proved a positive times a negative integer equals a negative integer. ${\displaystyle \blacksquare }$

A similar exercise can show that ${\displaystyle -x=(-1)x}$ and ${\displaystyle (-x)(-y)=xy}$. These two properties of multiplication allow us to keep the definition of multiplication the same for the set of integers. We will leave these two important "theorems" as non-trivial exercises for the reader.

Rational numbers start to break down the "repeated addition" idea of multiplication, since how can you add a number partially? Let us demonstrate the problem: Let ${\displaystyle a\in \mathbb {Q} }$ and ${\displaystyle b\in \mathbb {Q} }$. Allow four numbers to be defined as an integer that are relatively prime to the other — ${\displaystyle m}$, ${\displaystyle n}$, ${\displaystyle p}$, ${\displaystyle q}$. Let ${\displaystyle a={\frac {m}{n}}}$ and ${\displaystyle b={\frac {p}{q}}}$. If applied directly to our old definition, ${\displaystyle P(a,b)}$ would be asking us to a strange operation: add a fraction to itself "fractionally" many times. This is strange indeed. While we will not be discussing how we determined this formal definition below, keep in mind it took mathematicians more than simply writing this as true to be accepted into our lexicon, today:

${\displaystyle P(a,b)=ab={\frac {m}{n}}\cdot {\frac {p}{q}}{\overset {\underset {\mathrm {def} }{}}{=}}{\frac {mn}{pq}}}$.

The rational numbers definition does not contradict the old definition since each term therein is an integer, and thus, denominators for the terms are all ${\displaystyle 1}$. This means ${\displaystyle ab=mn=\underbrace {a+a+a+\cdots +a+a+a} _{b}=\underbrace {m+m+m+\cdots +m+m+m} _{n}}$. We will skip defining real numbers since it involves introducing information that you will not learn unless you enter into some more pure math besides College Algebra or even Calculus.

This recursive addition defines a new operation, requiring us to define more and more specific cases. This idea of recursive addition can be extended to subtraction (which makes division) and then multiplication itself. Through recursive multiplication one reaches the idea of the exponent. As you have in the past referred back to properties of multiplication to help you operate expressions, you too will apply these ideas to learn about properties of exponents.

## Definitions of Exponents (Form One)

As we referred to in the introduction to this page, exponent is an operation of repeated multiplication of the base ${\displaystyle a}$ over a period of ${\displaystyle p}$ times. The expression is often read aloud as ${\displaystyle a}$ to the power of ${\displaystyle p}$. Allowing the function ${\displaystyle e_{a}(p)}$, in which ${\displaystyle a\in \mathbb {N} }$ and ${\displaystyle p\in \mathbb {N} }$, to represent the exponent operation as follows,

${\displaystyle e_{a}(p)=\overbrace {a\cdot a\cdots a\cdot a} ^{p}{\overset {\underset {\mathrm {def} }{}}{=}}a^{p}}$

will let us see what properties might exist for natural numbers. Over more clarifications, the power function, so to speak, will lead to rules.

### Properties of Exponents (Under Form One)

Zero Power: ${\displaystyle e_{a}(0)=1}$ for ${\displaystyle a>0}$.

The function ${\displaystyle e_{a}(0)=a^{0}}$ for non-zero ${\displaystyle a}$ results in the following

${\displaystyle e_{a}(0)=a^{0}=1}$

The above result is true by definition although there is another way to think about this function. This type of thinking will be given later. For now, simply think this is true.

Product of Powers: ${\displaystyle e_{a}(n)\cdot e_{a}(m)}$ where ${\displaystyle n,m\in \mathbb {N} }$.

Given the two exponents ${\displaystyle e_{a}(n)=a^{n}}$ and ${\displaystyle e_{a}(m)=a^{m}}$, multiplying the two gives the following:

${\displaystyle a^{n}\cdot a^{m}=a^{n+m}}$
 Proof 2: ${\displaystyle a^{n}\cdot a^{m}=a^{n+m}}$ for ${\displaystyle a,n,m\in \mathbb {N} }$. This property of exponents can be proven by using the definition of exponent created herein. By definition, ${\displaystyle e_{a}(n)=a^{n}=\overbrace {a\cdot a\cdots a\cdot a} ^{n}}$ ${\displaystyle e_{a}(m)=a^{m}=\overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{m}}$ Therefore, in multiplying the two different functions, ${\displaystyle a^{n}\cdot a^{m}=\left(\overbrace {a\cdot a\cdots a\cdot a} ^{n}\right)\cdot \left(\overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{m}\right)}$ Because there are ${\displaystyle n}$ terms being multiplied to ${\displaystyle m}$ terms, every term therein has a base ${\displaystyle a}$, and multiplication is associative, it is safe to infer there are ${\displaystyle n+m}$ terms of ${\displaystyle a}$ being multiplied together. As such, ${\displaystyle a^{n}\cdot a^{m}=\underbrace {\overbrace {a\cdot a\cdots a\cdot a} ^{n}\cdot \overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{m}} _{n+m}=a^{n+m}}$
Quotient of Powers: ${\displaystyle {\frac {e_{a}(n)}{e_{a}(m)}}}$ where ${\displaystyle n,m\in \mathbb {N} }$.

Given the two exponents ${\displaystyle e_{a}(n)=a^{n}}$ and ${\displaystyle e_{a}(m)=a^{m}}$, dividing ${\displaystyle a^{n}}$ by ${\displaystyle a^{m}}$ for ${\displaystyle n>m}$ will give the following:

${\displaystyle {\frac {e_{a}(n)}{e_{a}(m)}}=a^{n-m}}$
 Proof 3: ${\displaystyle {\frac {a^{n}}{a^{m}}}=a^{n-m}}$ for ${\displaystyle a,n,m\in \mathbb {N} }$ and ${\displaystyle n>m}$. Keep in mind that because we are working with natural numbers, ${\displaystyle m\ngtr n}$. To keep everything in the natural numbers, this restriction must apply. Either way, let us continue by proving this property. By definition, ${\displaystyle e_{a}(n)=a^{n}=\overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{n}}$ ${\displaystyle e_{a}(m)=a^{m}=\overbrace {a\cdot a\cdots a\cdot a} ^{m}}$ In dividing the two different functions, ${\displaystyle {\frac {e_{a}(n)}{e_{a}(m)}}={\frac {\overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{n}}{\underbrace {a\cdot a\cdots a\cdot a} _{m}}}}$ Because there are ${\displaystyle n}$ terms being divided by ${\displaystyle m}$ terms of ${\displaystyle a}$, every term therein has a base ${\displaystyle a}$, and multiplication of the inverse operation is associative, it is safe to infer there are ${\displaystyle n-m}$ terms of ${\displaystyle a}$ after the division. This can further be shown through the operation as follows: all red terms are canceled and what is left over is the terms that are not canceled, ${\displaystyle n-m}$. ${\displaystyle {\frac {e_{a}(n)}{e_{a}(m)}}={\frac {{\color {red}\overbrace {a\cdot a\cdots a\cdot a} ^{m}}\cdot \overbrace {a\cdot a\cdots a} ^{n-m}}{\color {red}\underbrace {a\cdot a\cdots a\cdot a} _{m}}}}$ ${\displaystyle {\frac {e_{a}(n)}{e_{a}(m)}}=\overbrace {a\cdot a\cdots a} ^{n-m}}$ As such, ${\displaystyle {\frac {a^{n}}{a^{m}}}={\frac {\overbrace {a\cdot a\cdot a\cdots a\cdot a\cdot a} ^{n}}{\underbrace {a\cdot a\cdots a\cdot a} _{m}}}=\overbrace {a\cdot a\cdots a} ^{n-m}=a^{n-m}}$
Power of a power: ${\displaystyle \left(e_{a}(n)\right)^{m}}$ where ${\displaystyle n,m\in \mathbb {N} }$.

Given the exponent operation ${\displaystyle e_{a}(n)=a^{n}}$, for any ${\displaystyle n,m\in \mathbb {N} }$ such that ${\displaystyle n,m>0}$

${\displaystyle \left(e_{a}(n)\right)^{m}=\left(a^{n}\right)^{m}=a^{n\cdot m}}$.

For any operation that results in ${\displaystyle n\cdot m=0}$, ${\displaystyle a\neq 0}$.

 Proof 4: ${\displaystyle \left(e_{a}(n)\right)^{m}=\left(a^{n}\right)^{m}=a^{n\cdot m}}$ for ${\displaystyle a,n,m\in \mathbb {N} }$ and ${\displaystyle n,m>0}$. This second-to-last rule has a pretty involved intuition behind it. Be sure to follow along: ${\displaystyle e_{a}(n)=a^{n}=\overbrace {a\cdot a\cdots a\cdot a} ^{n}}$ ${\displaystyle e_{b}(m)=b^{m}=\overbrace {b\cdot b\cdot b\cdots b\cdot b\cdot b} ^{m}}$ If ${\displaystyle b=a^{n}}$, then ${\displaystyle e_{a^{n}}(m)=\left(a^{n}\right)^{m}}$. By the second bullet point above: ${\displaystyle e_{a^{n}}(m)=\left(a^{n}\right)^{m}=\overbrace {a^{n}\cdot a^{n}\cdot a^{n}\cdots a^{n}\cdot a^{n}\cdot a^{n}} ^{m}=\overbrace {\left(\overbrace {a\cdot a\cdots a\cdot a} ^{n}\right)\cdots \left(\overbrace {a\cdot a\cdots a\cdot a} ^{n}\right)} ^{m}}$ Pay close attention to what this operation is telling us: there ${\displaystyle n}$ many constants ${\displaystyle a}$ multiplied to itself, for which this operation repeats ${\displaystyle m}$ times. Because ${\displaystyle n}$ factors of ${\displaystyle a}$ are multiplied again to itself as its operation ${\displaystyle m}$ many times, there ${\displaystyle n\cdot m}$ of those factors in total. As such: ${\displaystyle \left(a^{n}\right)^{m}=\overbrace {a^{n}\cdot a^{n}\cdot a^{n}\cdots a^{n}\cdot a^{n}\cdot a^{n}} ^{m}=\overbrace {\left(\overbrace {a\cdot a\cdots a\cdot a} ^{n}\right)\cdots \left(\overbrace {a\cdot a\cdots a\cdot a} ^{n}\right)} ^{m}=a^{n\cdot m}}$
Multiples of Base: ${\displaystyle e_{ab}(n)}$ where ${\displaystyle a,b,n\in \mathbb {N} }$.

Given the exponent operation ${\displaystyle e_{ab}(n)=(ab)^{n}}$, for any ${\displaystyle a,b,n\in \mathbb {N} }$

${\displaystyle e_{ab}(n)=a^{n}b^{n}}$.
 Proof 5: ${\displaystyle e_{ab}(n)=a^{n}b^{n}}$ for ${\displaystyle a,b,n\in \mathbb {N} }$. This will be the simplest proof in this chapter. All that will be needed is the definition of an exponent; specifically, the one that states the operation is simply repeated multiplication. We are given the following: ${\displaystyle e_{ab}(n)=(ab)^{n}=\overbrace {ab\cdot ab\cdots ab\cdot ab} ^{n}}$ Because multiplication is associative, ${\displaystyle \overbrace {ab\cdot ab\cdots ab\cdot ab} ^{n}=\overbrace {a\cdot a\cdots a\cdot a} ^{n}\cdot \overbrace {b\cdot b\cdots b\cdot b} ^{n}}$ From this, we learn that ${\displaystyle (ab)^{n}=\overbrace {ab\cdot ab\cdots ab\cdot ab} ^{n}=\overbrace {a\cdot a\cdots a\cdot a} ^{n}\cdot \overbrace {b\cdot b\cdots b\cdot b} ^{n}=a^{n}b^{n}}$


text:
## Serum-derived factors of breast cancer patients with brain metastases alter permeability of a human blood-brain barrier model

Please always quote using this URN: urn:nbn:de:bvb:20-opus-229940
• Background The most threatening metastases in breast cancer are brain metastases, which correlate with a very poor overall survival, but also a limited quality of life. A key event for the metastatic progression of breast cancer into the brain is the migration of cancer cells across the blood-brain barrier (BBB). Methods We adapted and validated the CD34$$^+$$ cells-derived human in vitro BBB model (brain-like endothelial cells, BLECs) to analyse the effects of patient serum on BBB properties. We collected serum samples from healthyBackground The most threatening metastases in breast cancer are brain metastases, which correlate with a very poor overall survival, but also a limited quality of life. A key event for the metastatic progression of breast cancer into the brain is the migration of cancer cells across the blood-brain barrier (BBB). Methods We adapted and validated the CD34$$^+$$ cells-derived human in vitro BBB model (brain-like endothelial cells, BLECs) to analyse the effects of patient serum on BBB properties. We collected serum samples from healthy donors, breast cancer patients with primary cancer, and breast cancer patients with, bone, visceral or cerebral metastases. We analysed cytokine levels in these sera utilizing immunoassays and correlated them with clinical data. We used paracellular permeability measurements, immunofluorescence staining, Western blot and mRNA analysis to examine the effects of patient sera on the properties of BBB in vitro. Results The BLECs cultured together with brain pericytes in transwells developed a tight monolayer with a correct localization of claudin-5 at the tight junctions (TJ). Several BBB marker proteins such as the TJ proteins claudin-5 and occludin, the glucose transporter GLUT-1 or the efflux pumps PG-P and BCRP were upregulated in these cultures. This was accompanied by a reduced paracellular permeability for fluorescein (400 Da). We then used this model for the treatment with the patient sera. Only the sera of breast cancer patients with cerebral metastases had significantly increased levels of the cytokines fractalkine (CX3CL1) and BCA-1 (CXCL13). The increased levels of fractalkine were associated with the estrogen/progesterone receptor status of the tumour. The treatment of BLECs with these sera selectively increased the expression of CXCL13 and TJ protein occludin. In addition, the permeability of fluorescein was increased after serum treatment. Conclusion We demonstrate that the CD34$$^+$$ cell-derived human in vitro BBB model can be used as a tool to study the molecular mechanisms underlying cerebrovascular pathologies. We showed that serum from patients with cerebral metastases may affect the integrity of the BBB in vitro, associated with elevated concentrations of specific cytokines such as CX3CL1 and CXCL13.

format: plain


text:
Is there a tricategory of bicategories and biprofunctors? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:38:44Z http://mathoverflow.net/feeds/question/36830 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36830/is-there-a-tricategory-of-bicategories-and-biprofunctors Is there a tricategory of bicategories and biprofunctors? Evan Jenkins 2010-08-27T01:08:55Z 2013-02-04T23:49:04Z
Background

There is a bicategory where the objects are categories, the 1-morphisms are profunctors, and the 2-morphisms are morphisms of profunctors. The non-obvious part of this assertion is that profunctors admit a "good" (i.e., coherently associative) composition. The way one sees this is to use the fact that the Yoneda embedding is the free cocompletion, from which we may identify profunctors from $\mathcal{C}$ to $\mathcal{D}$ with cocontinuous functors from $\operatorname{Set}^{\mathcal{C}^{\operatorname{op}}}$ to $\operatorname{Set}^{\mathcal{D}^{\operatorname{op}}}$. Over here, there is a strictly associative composition, so life is good.

All of this extends easily to the enriched setting. In particular, if we enrich over $\mathcal{V} = \operatorname{Cat}$, we can talk about strict 2-profunctors between strict 2-categories, and we get a nice bicategory of 2-categories, strict 2-profunctors, and morphisms between these.

Question

I would like to know if there is an analogous way to obtain a tricategory of bicategories and biprofunctors. You can "follow your nose" and write down what the composition should be, but checking all the axioms of a tricategory does not seem like the simplest approach. Of course, we can strictify to get equivalent strict 2-categories and 2-profunctors, but I doubt the composition will be the same; I don't think the "strict" colimits will in general agree with the "weak" colimits. Also, using the standard enriched theory only gives a bicategory; the natural transformations are lost. It seems that an appropriate statement of the form "the bicategorical Yoneda embedding is a free cocompletion" will handle things just as it does in the setting of ordinary profunctors, but I am not sufficiently comfortable with limits and colimits in bicategories to try to figure out if such a statement makes sense. Has anybody worked all of this out?

(The closest thing I have seen to such a result is this paper by Justin Greenough, which more or less establishes this result in the case of sufficiently nice $k$-linear monoidal categories. But his proof seems to be very specific to that setting, whereas one would hope that a proof could be established along the same lines as the result for usual profunctors.)
 http://mathoverflow.net/questions/36830/is-there-a-tricategory-of-bicategories-and-biprofunctors/36881#36881 Answer by Urs Schreiber for Is there a tricategory of bicategories and biprofunctors? Urs Schreiber 2010-08-27T12:45:11Z 2010-08-27T12:45:11Z
Depending on what you actually need for your application, there might be something useful already known. Do you really need a tricategory, as opposed to some other model of weak 3-categories? Even if you had that, would you be able to do much with it?

There are several equivalent ways to think of profunctors, and some of them lend themselves to categorification quite easily. One is this:

A profunctor from $C$ to $D$ is the same a a colimit-preserving ordinary functor between the presheaf categories $PSh(C)$ and $PSh(D)$.

(See here for details: http://ncatlab.org/nlab/show/profunctor#FuncsOnPresheaves)

That's good, because a lot is known about categorifications of categories of presheaves and of morphisms between them.

For instance it is straightforward to set this up over bicategories: take objects bicategories, and hom-bicategories to be the full sub-bicategory on bicolimit-preserving bifunctors between their bipresheaf categories.

In case that your application is such that you only need higher categories whose higher morphisms are all invertible, one can go much further and consider the (oo,1)-category of (oo,1)-profunctors. By the above, this is simply the gadget whose objects are small (oo,1)-categories and whose hom-oo-groupoids are the full sub-oo-groupoids on the (oo,1)-colimit preserving (oo,1)-functors between the corresponding (oo,1)-presheaf categories.

More generally, one can generalize here (oo,1)-presheaf categories and all in addition all their reflective sub-(oo,1)-categories. That structure of (oo,1)-profunctors has proven to play a major role as kind of categorification of the category of vector spaces: one thinks of a presentable (oo,1)-category as vector space, of colimits as being sums of vectors, as colimit preserving (oo,1)-functors as linear maps.

More on this is here: http://ncatlab.org/nlab/show/Pr(infinity,1)Cat .
 http://mathoverflow.net/questions/36830/is-there-a-tricategory-of-bicategories-and-biprofunctors/66237#66237 Answer by Finn Lawler for Is there a tricategory of bicategories and biprofunctors? Finn Lawler 2011-05-27T21:59:59Z 2011-05-27T21:59:59Z
If you're still interested, I've worked this out on my personal web at nLab here, with supporting material linked to from this page.
 http://mathoverflow.net/questions/36830/is-there-a-tricategory-of-bicategories-and-biprofunctors/120811#120811 Answer by Mike Shulman for Is there a tricategory of bicategories and biprofunctors? Mike Shulman 2013-02-04T23:49:04Z 2013-02-04T23:49:04Z
This recent paper comes within about $3\epsilon$ of constructing the tricategory of enriched bicategories and enriched profunctors. I'm kind of sad that we didn't get around to crossing the remaining distance.


text:
Feeds:
Posts

## Implementation and Abstraction in Mathematics

I recently noticed on arXiv that the following manuscript “Implementation and Abstraction in Mathematics” by David McAllester. A couple of years ago, I had taken a graduate course taught by David that had a similar flavour (the material in the manuscript is more advanced, in particular the main results, not to mention it is better organized and the presentation more polished), presenting a type theoretic foundation of mathematics. Although I can’t say I did very well in the course, I certainly enjoyed the ideas in it very much, and thus the above manuscript might be worth a look. Perhaps it might be a good idea to audit that course again, just to make sure I understand the main ideas better this time. :)

## Some Proofs of the Cauchy-Schwarz Inequality

Over the past 4-5 months whenever there is some time to spare, I have been working through The Cauchy-Schwarz Master Class by J. Michael Steele. And, although I am still left with the last two chapters, I have been reflecting on the material already covered in order to get a better perspective on what I have been slowly learning over the months. This blog post is a small exercise in this direction.

Ofcourse, there is nothing mysterious about proving the Cauchy-Schwarz inequality; it is fairly obvious and basic. But I thought it still might be instructive (mostly to myself) to reproduce some proofs that I know out of memory (following a maxim of my supervisor on a white/blackboard blogpost). Although, why Cauchy-Schwarz keeps appearing all the time and what makes it so useful and fundamental is indeed quite interesting and non-obvious. And like Gil Kalai notes, it is also unclear why is it that it is Cauchy-Schwarz which is mainly useful. I feel that Steele’s book has made me appreciate this importance somewhat more (compared to 4-5 months ago) by drawing to many concepts that link back to Cauchy-Schwarz.

Before getting to the post, a word on the book: This book is perhaps amongst the best mathematics book that I have seen in many years. True to its name, it is indeed a Master Class and also truly addictive. I could not put aside the book completely once I had picked it up and eventually decided to go all the way. Like most great books, the way it is organized makes it “very natural” to rediscover many susbtantial results (some of them named) appearing much later by yourself, provided you happen to just ask the right questions. The emphasis on problem solving makes sure you make very good friends with some of the most interesting inequalities. The number of inequalities featured is also extensive. It starts off with the inequalities dealing with “natural” notions such as monotonicity and positivity and later moves onto somewhat less natural notions such as convexity. I can’t recommend this book enough!

Now getting to the proofs: Some of these proofs appear in Steele’s book, mostly as either challenge problems or as exercises. All of them were solvable after some hints.

________________

Proof 1: A Self-Generalizing proof

This proof is essentially due to Titu Andreescu and Bogdan Enescu and has now grown to be my favourite Cauchy-Schwarz proof.

We start with the trivial identity (for $a, b \in \mathbb{R}, x >0, y>0$):

Identity 1: $(ay - bx)^2 \geq 0$

Expanding we have

$a^2y^2 + b^2x^2 - 2abxy \geq 0$

Rearranging this we get:

$\displaystyle \frac{a^2y}{x} + \frac{b^2x}{y} \geq 2ab$

Further: $\displaystyle a^2 + b^2 + \frac{a^2y}{x} + \frac{b^2x}{y} \geq (a+b)^2$;

Rearranging this we get the following trivial Lemma:

Lemma 1: $\displaystyle \frac{(a+b)^2}{(x+y)} \leq \frac{a^2}{x} + \frac{b^2}{y}$

Notice that this Lemma is self generalizing in the following sense. Suppose we replace $b$ with $b + c$ and $y$ with $y + z$, then we have:

$\displaystyle \frac{(a+b+c)^2}{(x+y+z)} \leq \frac{a^2}{x} + \frac{(b+c)^2}{y+z}$

But we can apply Lemma 1 to the second term of the right hand side one more time. So we would get the following inequality:

$\displaystyle \frac{(a+b+c)^2}{(x+y+z)} \leq \frac{a^2}{x} + \frac{b^2}{y} + \frac{c^2}{z}$

Using the same principle $n$ times we get the following:

$\displaystyle \frac{(a_1+a_2+ \dots a_n)^2}{(x_1+x_2+ \dots + x_n)} \leq \frac{a_1^2}{x_1} + \frac{a_2^2}{x_2} + \dots + \frac{a_n^2}{x_n}$

Now substitute $a_i = \alpha_i \beta_i$ and $x_i = \beta_i^2$ to get:

$\displaystyle ( \sum_{i=1}^n \alpha_i \beta_i )^2 \leq \sum_{i=1}^n ( \alpha_i )^2 \sum_{i=1}^n ( \beta_i )^2$

This is just the Cauchy-Schwarz Inequality, thus completing the proof.

________________

Proof 2: By Induction

Again, the Cauchy-Schwarz Inequality is the following: for $a, b \in \mathbb{R}$

$\displaystyle ( \sum_{i=1}^n a_i b_i )^2 \leq \sum_{i=1}^n ( a_i )^2 \sum_{i=1}^n ( b_i )^2$

For proof of the inequality by induction, the most important thing is starting with the right base case. Clearly $n = 1$ is trivially true, suggesting that it is perhaps not of much import. So we consider the case for $n = 2$. Which is:

$\displaystyle ( a_1 b_1 + a_2 b_2 )^2 \leq ( a_1^2 + a_2^2 ) (b_1^2 + b_2^2)$

To prove the base case, we simply expand the expressions. To get:

$\displaystyle a_1^2 b_1^2 + a_2^2 b_2^2 + 2 a_1 b_1 a_2 b_2 \leq a_1^2 b_1^2 + a_1^2 b_2^2 + a_2^2 b_1^2 + a_2^2 b_2^2$

Which is just:

$\displaystyle a_1^2 b_2^2 + a_2^2 b_1^2 - 2 a_1 b_1 a_2 b_2 \geq 0$

Or:

$\displaystyle (a_1 b_2 - a_2 b_1 )^2 \geq 0$

Which proves the base case.

Moving ahead, we assume the following inequality to be true:

$\displaystyle ( \sum_{i=1}^k a_i b_i )^2 \leq \sum_{i=1}^k ( a_i )^2 \sum_{i=1}^k ( b_i )^2$

To establish Cauchy-Schwarz, we have to demonstrate, assuming the above, that

$\displaystyle ( \sum_{i=1}^{k+1} a_i b_i )^2 \leq \sum_{i=1}^{k+1} ( a_i )^2 \sum_{i=1}^{k+1} ( b_i )^2$

So, we start from $H(k)$:

$\displaystyle ( \sum_{i=1}^k a_i b_i )^2 \leq \sum_{i=1}^k ( a_i )^2 \sum_{i=1}^k ( b_i )^2$

we further have,

$\displaystyle \Big(\sum_{i=1}^k a_i b_i\Big) + a_{k+1}b_{k+1} \leq \Big(\sum_{i=1}^k ( a_i )^2\Big)^{1/2} \Big(\sum_{i=1}^k ( b_i )^2\Big)^{1/2} + a_{k+1}b_{k+1} \ \ \ \ (1)$

Now, we can apply the case for $n = 2$. Recall that: $\displaystyle a_1 b_1 + a_2 b_2 \leq (a_1^2 + a_2^2)^{1/2} (b_1^2 + b_2^2)^{1/2}$

Thus, using this in the R. H. S of $(1)$, we would now have:

$\displaystyle \Big(\sum_{i=1}^{k+1} a_i b_i\Big) \leq \Big(\sum_{i=1}^k ( a_i )^2 + a_{k+1}^2\Big)^{1/2} \Big(\sum_{i=1}^k ( b_i )^2 + b_{k+1}^2\Big)^{1/2}$

Or,

$\displaystyle \Big(\sum_{i=1}^{k+1} a_i b_i\Big) \leq \Big(\sum_{i=1}^{k+1} ( a_i )^2 \Big)^{1/2} \Big(\sum_{i=1}^{k+1} ( b_i )^2 \Big)^{1/2}$

This proves the case $H(k+1)$ on assuming $H(k)$. Thus also proving the Cauchy-Schwarz inequality by the principle of mathematical induction.

________________

Proof 3: For Infinite Sequences using the Normalization Trick:

Problem: For $a, b \in \mathbb{R}$ If $\displaystyle \Big(\sum_{i=1}^{\infty} a_i^2 \Big) < \infty$ and $\displaystyle \Big(\sum_{i=1}^{\infty} b_i^2 \Big) < \infty$ then is $\displaystyle \Big(\sum_{i=1}^{\infty} |a_i||b_i|\Big) < \infty$ ?

Note that this is easy to establish. We simply start with the trivial identity $(x-y)^2 \geq 0$ which in turn gives us $\displaystyle xy \leq \frac{x^2}{2} + \frac{y^2}{2}$

Next, take $x = |a_i|$ and $y = |b_i|$ on summing up to infinity on both sides, we get the following:

$\displaystyle \Big( \sum_{i=1}^{\infty} |a_i||b_i| \Big)^2 \leq \frac{1}{2}\Big(\sum_{i=1}^{\infty} a_i^2\Big) + \frac{1}{2} \Big(\sum_{i=1}^{\infty} b_i^2\Big)\ \ \ \ \ \ \ \ (2)$

From this it immediately follows that

$\displaystyle \Big(\sum_{i=1}^{\infty} |a_i||b_i|\Big) < \infty$

Now let

$\displaystyle \hat{a}_i = \frac{a_i}{\Big(\sum_j a_i^2\Big)^{1/2}}$ and

$\displaystyle \hat{b}_i = \frac{b_i}{\Big(\sum_j b_i^2\Big)^{1/2}}$; substituting in $(2)$, we get:

$\displaystyle \Big( \sum_{i=1}^{\infty} |\hat{a}_i||\hat{b}_i| \Big)^2 \leq \frac{1}{2}\Big(\sum_{i=1}^{\infty} \hat{a}_i^2\Big) + \frac{1}{2} \Big(\sum_{i=1}^{\infty} \hat{b}_i^2\Big)$ or,

$\displaystyle \Bigg(\sum_{i = 1}^{\infty}\frac{a_i}{\Big(\sum_j a_j^2\Big)^{1/2}}\frac{b_i}{\Big(\sum_j b_j^2\Big)^{1/2}}\Bigg)^2 \leq \frac{1}{2} + \frac{1}{2}$

Which simply gives back Cauchy’s inequality for infinite sequences thus completing the proof:

$\displaystyle \Big(\sum_{i=1}^{\infty} a_i b_i\Big)^2 \leq \Big(\sum_{i=1}^{\infty}a_i^2\Big) \Big(\sum_{i=1}^{\infty}b_i^2\Big)$

________________

Proof 4: Using Lagrange’s Identity

We first start with a polynomial which we denote by $\mathbf{Q}_n$:

$\mathbf{Q}_n = \big(a_1^2 + a_2^2 + \dots + a_n^2 \big) \big(b_1^2 + b_2^2 + \dots + b_n^2 \big) - \big(a_1b_1 + a_2b_2 + \dots + a_nb_n\big)^2$

The question to now ask, is $\mathbf{Q}_n \geq 0$? To answer this question, we start of by re-writing $\mathbf{Q}_n$ in a “better” form.

$\displaystyle \mathbf{Q}_n = \sum_{i=1}^{n}\sum_{j=1}^{n} a_i^2 b_j^2 - \sum_{i=1}^{n}\sum_{j=1}^{n} a_ib_i a_jb_j$

Next, as J. Michael Steele puts, we pursue symmetry and rewrite the above so as to make it apparent.

$\displaystyle \mathbf{Q}_n = \frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} \big(a_i^2 b_j^2 + a_j^2 b_i^2\big) - \frac{2}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} a_ib_i a_jb_j$

Thus, we now have:

$\displaystyle \mathbf{Q}_n = \frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} \big(a_i b_j - a_j b_i\big)^2$

This makes it clear that $\mathbf{Q}_n$ can be written as a sum of squares and hence is always postive. Let us write out the above completely:

$\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n} a_i^2 b_j^2 - \sum_{i=1}^{n}\sum_{j=1}^{n} a_ib_ib_jb_j = \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \big(a_ib_j -a_jb_i\big)^2$

Now, reversing the step we took at the onset to write the L.H.S better, we simply have:

$\displaystyle \sum_{i}^{n} a_i^2 \sum_{}^{n} b_i^2 - \big(\sum_{i=1}^n a_ib_i\big)^2 = \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \big(a_ib_j -a_jb_i\big)^2$

This is called Lagrange’s Identity. Now since the R.H.S. is always greater than or equal to zero. We get the following inequality as a corrollary:

$\displaystyle \big(\sum_{i=1}^n a_ib_i\big)^2 \leq \sum_{i}^{n} a_i^2 \sum_{}^{n} b_i^2$

This is just the Cauchy-Schwarz inequality, completing the proof.

________________

Proof 5: Gram-Schmidt Process gives an automatic proof of Cauchy-Schwarz

First we quickly review the Gram-Schmidt Process: Given a set of linearly independent elements of a real or complex inner product space $\big(V,\langle\cdot, \cdot\rangle\big)$, $\mathbf{x_1}, \mathbf{x_2}, \dots, \mathbf{x_n}$. We can get an orthonormal set of $n$ elemets $\mathbf{e_1}, \mathbf{e_2}, \dots, \mathbf{e_n}$ by the simple recursion (after setting $\displaystyle \mathbf{e_1 = \frac{\mathbf{x_1}}{\|x_1 \|}}$).

$\displaystyle \mathbf{z_k} = \mathbf{x_k} - \sum_{j=1}^{k-1} \langle\mathbf{x_k},\mathbf{e_j}\rangle\mathbf{e_j}$ and then

$\displaystyle \mathbf{e_k} = \frac{\mathbf{z_k}}{\|\mathbf{z_k}\|}$

for $k = 2, 3, \dots, n$.

Keeping the above in mind, assume that $\| x\| = 1$. Now let $x = e_1$. Thus, we have:

$\mathbf{z} = \mathbf{y} - \langle \mathbf{y}, \mathbf{e_1}\rangle\mathbf{e_1}$

Giving: $\displaystyle \mathbf{e_2} = \frac{\mathbf{z}}{\|\mathbf{z}\|}$. Rearranging we have:

$\displaystyle \|\mathbf{z}\|\mathbf{e_2} = \mathbf{y} - \langle \mathbf{y}, \mathbf{e_1}\rangle\mathbf{e_1}$ or

$\displaystyle \mathbf{y} = \langle \mathbf{y},\mathbf{e_1}\rangle \mathbf{e_1} + \|\mathbf{z}\|\mathbf{e_2}$ or

$\displaystyle \mathbf{y} = \mathbf{c_1} \mathbf{e_1} + \mathbf{c_2}\mathbf{e_2}$ where $c_1, c_2$ are constants.

Now note that: $\displaystyle \langle\mathbf{x},\mathbf{y}\rangle = c_1$ and

$\displaystyle \langle \mathbf{y},\mathbf{y}\rangle = |c_1|^2 + |c_2|^2$. The following bound is trivial:

$\displaystyle |c_1| \leq (|c_1|^2 + |c_2|^2)^{1/2}$. But note that this is simply $\langle x,y \rangle \leq \langle y,y \rangle^{1/2}$

Which is just the Cauchy-Schwarz inequality when $\|x\| = 1$.

________________

Proof 6: Proof of the Continuous version for d =2; Schwarz’s Proof

For this case, the inequality may be stated as:

Suppose we have $S \subset \mathbb{R}^2$ and that $f: S \to \mathbb{R}$ and $g: S \to \mathbb{R}$. Then consider the double integrals:

$\displaystyle A = \iint_S f^2 dx dy$, $\displaystyle B = \iint_S fg dx dy$ and $\displaystyle C = \iint_S g^2 dx dy$. These double integrals must satisfy the following inequality:

$|B| \leq \sqrt{A} . \sqrt{C}$.

The proof given by Schwarz as is reported in Steele’s book (and indeed in standard textbooks) is based on the following observation:

The real polynomial below is always non-negative:

$\displaystyle p(t) = \iint_S \Big( t f(x,y) + g(x,y) \Big)^2 dx dy = At^2 + 2Bt + C$

$p(t) > 0$ unless $f$ and $g$ are proportional. Thus from the binomial formula we have that $B^2 \leq AC$, moreover the inequality is strict unless $f$ and $g$ are proportional.

________________

Proof 7: Proof using the Projection formula

Problem: Consider any point $x \neq 0$ in $\mathbb{R}^d$. Now consider the line that passes through this point and origin. Let us call this line $\mathcal{L} = \{ tx: t \in \mathbb{R}\}$. Find the point on the line closest to any point $v \in \mathbb{R}^d$.

If $P(v)$ is the point on the line that is closest to $v$, then it is given by the projection formula: $\displaystyle P(v) = x \frac{\langle x, v \rangle }{\langle x, x \rangle}$

This is fairly elementary to establish. To find the value of $t$, such that distance $\rho(v,tx)$ is minimized, we can simply consider the squared distance $\rho^2(v,tx)$ since it is easier to work with. Which by definition is:

$\displaystyle \rho^2(v,tx) = \langle v - x, v - tx \rangle$

which is simply:

$\displaystyle \rho^2(v,tx) = \langle v, v \rangle - 2t \langle v, x \rangle + t^2 \langle x, x \rangle$

$\displaystyle = \langle x, x \rangle \bigg( t^2 -2t \frac{\langle v, x \rangle}{\langle x, x \rangle} + \frac{\langle v, v \rangle}{\langle x, x \rangle}\bigg)$

$\displaystyle = \langle x, x \rangle \bigg\{ \bigg(t - \frac{\langle v,x \rangle}{\langle x,x \rangle}\bigg)^2 - \frac{\langle v,x \rangle^2}{\langle x,x \rangle^2}\bigg\} + \frac{\langle v, v \rangle}{\langle x, x \rangle}\bigg)$

$\displaystyle = \langle x, x \rangle \bigg\{ \bigg(t - \frac{\langle v,x \rangle}{\langle x,x \rangle}\bigg)^2 - \frac{\langle v,x \rangle^2}{\langle x,x \rangle^2} + \frac{\langle v, v \rangle}{\langle x, x \rangle} \bigg\}$

$\displaystyle = \langle x, x \rangle \bigg\{ \bigg(t - \frac{\langle v,x \rangle}{\langle x,x \rangle}\bigg)^2 - \frac{\langle v,x \rangle^2}{\langle x,x \rangle^2} + \frac{\langle v, v \rangle \langle x, x \rangle}{\langle x, x \rangle^2} \bigg\}$

So, the value of $t$ for which the above is minimized is $\displaystyle \frac{\langle v,x \rangle}{\langle x,x \rangle}$. Note that this simply reproduces the projection formula.

Therefore, the minimum squared distance is given by the expression below:

$\displaystyle \min_{t \in \mathbb{R}} \rho^2(v, tx) = \frac{\langle v,v\rangle \langle x,x \rangle - \langle v,x \rangle^2}{\langle x,x \rangle}$

Note that the L. H. S is always positive. Therefore we have:

$\displaystyle \frac{\langle v,v\rangle \langle x,x \rangle - \langle v,x \rangle^2}{\langle x,x \rangle} \geq 0$

Rearranging, we have:

$\displaystyle \langle v,x \rangle^2 \leq \langle v,v\rangle \langle x,x \rangle$

Which is just Cauchy-Schwarz, thus proving the inequality.

________________

Proof 8: Proof using an identity

A variant of this proof is amongst the most common Cauchy-Schwarz proofs that are given in textbooks. Also, this is related to proof (6) above. However, it still has some value in its own right. While also giving an useful expression for the “defect” for Cauchy-Schwarz like the Lagrange Identity above.

$P(t) = \langle v - tw, v - tw \rangle$. Clearly $P(t) \geq 0$.

To find the minimum of this polynomial we find its derivative w.r.t $t$ and setting to zero:

$P'(t) = 2t \langle w, w \rangle - 2 \langle v, w \rangle = 0$ giving:

$\displaystyle t_0 = \frac{\langle v, w \rangle}{\langle w, w \rangle}$

Clearly we have $P(t) \geq P(t_0) \geq 0$. We consider:

$P(t_0) \geq 0$, substituting $\displaystyle t_0 = \frac{\langle v, w \rangle}{\langle w, w \rangle}$ we have:

$\displaystyle \langle v,v \rangle - \frac{\langle v, w \rangle}{\langle w, w \rangle} \langle v,w \rangle - \frac{\langle v, w \rangle}{\langle w, w \rangle} \langle w,v \rangle + \frac{\langle v, w \rangle^2}{\langle w, w \rangle^2}\langle w,w \rangle \geq 0 \ \ \ \ \ \ \ \ (A)$

Just rearrangine and simplifying:

$\displaystyle \langle v,v \rangle \langle w,w \rangle - \langle v, w \rangle^2 \geq 0$

This proves Cauchy-Schwarz inequality.

Now suppose we are interested in an expression for the defect in Cauchy-Schwarz i.e. the difference $\displaystyle \langle v,v \rangle \langle w,w \rangle - \langle v, w \rangle^2$. For this we can just consider the L.H.S of equation $(A)$ since it is just $\displaystyle \langle w,w \rangle \Big(\langle v,v \rangle \langle w,w \rangle - \langle v, w \rangle^2\Big)$.

i.e. Defect =

$\displaystyle \langle w,w \rangle \bigg(\langle v,v \rangle - 2 \frac{\langle v,w \rangle^2}{\langle w,w \rangle} + \frac{\langle v,w \rangle^2}{\langle w,w \rangle}\bigg)$

Which is just:

$\displaystyle \langle w,w \rangle\bigg(\Big\langle v - \frac{\langle w,v \rangle}{\langle w,w \rangle}w,v - \frac{\langle w,v \rangle}{\langle w,w \rangle}w \Big\rangle\bigg)$

This defect term is much in the spirit of the defect term that we saw in Lagrange’s identity above, and it is instructive to compare them.

________________

Proof 9: Proof using the AM-GM inequality

Let us first recall the AM-GM inequality:

For non-negative reals $x_1, x_2, \dots x_n$ we have the following basic inequality:

$\displaystyle \sqrt[n]{x_1 x_2 \dots x_n} \leq \Big(\frac{x_1 + x_2 + \dots x_n}{n}\Big)$.

Now let us define $\displaystyle A = \sqrt{a_1^2 + a_2^2 + \dots + a_n^2}$ and $\displaystyle B = \sqrt{b_1^2 + b_2^2 + \dots + b_n^2}$

Now consider the trivial bound (which gives us the AM-GM): $(x-y)^2 \geq 0$, which is just $\displaystyle \frac{1}{2}\Big(x^2 + y^2\Big) \geq xy$. Note that AM-GM as stated above for $n = 2$ is immediate when we consider $x \to \sqrt{x}$ and $y \to \sqrt{y}$

Using the above, we have:

$\displaystyle \frac{1}{2} \Big(\frac{a_i^2}{A^2} + \frac{b_i^2}{B^2}\Big) \geq \frac{a_ib_i}{AB}$

Summing over $n$, we have:

$\displaystyle \sum_{i=1}^n\frac{1}{2} \Big(\frac{a_i^2}{A^2} + \frac{b_i^2}{B^2}\Big) \geq \sum_{i=1}^n \frac{a_ib_i}{AB}$

But note that the L.H.S equals 1, therefore:

$\displaystyle \sum_{i=1}^n \frac{a_ib_i}{AB} \leq 1$ or $\displaystyle \sum_{i=1}^n a_ib_i \leq AB$

Writing out $A$ and $B$ as defined above, we have:

$\displaystyle \sum_{i=1}^n a_ib_i \leq \sqrt{\sum_{i=1}^na_i^2}\sqrt{\sum_{i=1}^nb_i^2}$.

Thus proving the Cauchy-Schwarz inequality.

________________

Proof 10: Using Jensen’s Inequality

We begin by recalling Jensen’s Inequality:

Suppose that $f: [p, q] \to \mathbb{R}$ is a convex function. Also suppose that there are non-negative numbers $p_1, p_2, \dots, p_n$ such that $\displaystyle \sum_{i=1}^{n} p_i = 1$. Then for all $x_i \in [p, q]$ for $i = 1, 2, \dots, n$ one has:

$\displaystyle f\Big(\sum_{i=1}^{n}p_ix_i\Big) \leq \sum_{i=1}^{n}p_if(x_i)$.

Now we know that $f(x) = x^2$ is convex. Applying Jensen’s Inequality, we have:

$\displaystyle \Big(\sum_{i=1}^{n} p_i x_i \Big)^2 \leq \sum_{i=1}^{n} p_i x_i^2$

Now, for $b_i \neq 0$ for all $i = 1, 2, \dots, n$, let $\displaystyle x_i = \frac{a_i}{b_i}$ and let $\displaystyle p_i = \frac{b_i^2}{\sum_{i=1}^{n}b_i^2}$.

Which gives:

$\displaystyle \Big(\sum_{i=1}^n \frac{a_ib_i}{\sum_{i=1}^{n}b_i^2}\Big)^2 \leq \Big(\sum_{i=1}^{n}\frac{a_i^2}{\sum_{i=1}^{n}b_i^2}\Big)$

Rearranging this just gives the familiar form of Cauchy-Schwarz at once:

$\displaystyle \Big(\sum_{i=1}^{n} a_ib_i\Big)^2 \leq \Big(\sum_{i=1}^{n} a_i^2\Big)\Big(\sum_{i=1}^{n} b_i^2\Big)$

________________

Proof 11: Pictorial Proof for d = 2

Here (page 4) is an attractive pictorial proof by means of tilings for the case $d = 2$ by Roger Nelson.

________________

## Gian-Carlo Rota on Combinatorics

The writings (and even papers/technical books) of Gian-Carlo Rota are perhaps amongst the most insightful that I have encountered in the past 3-4 years (maybe even more). Rota wrote to provoke, never resisting to finish a piece of writing with a rhetorical flourish even at the cost of injecting seeming inconsistency in his stance. I guess this is what you get when you have a first rate mathematician and philosopher endowed with an elegant; at times even devastating turn of phrase, with a huge axe to grind*.

The wisdom of G. C. Rota is best distilled in his book of essays, reviews and other thoughts: Indiscrete Thoughts and to some extent Discrete Thoughts. Perhaps I should review Indiscrete Thoughts in the next post, just to revisit some of those writings and my notes from them myself.

Rota in 1962

This post however is not about his writing in general as the title indicates. I recently discovered this excellent dialogue between Rota and David Sharp (1985). I found this on a lead from this László Lovász interview. Here he mentions that Rota’s combinatorics papers were an inspiration for him in his work to find more structure in combinatorics. From the David Sharp interview, here are two relevant excerpts (here too the above mentioned flourish is evident):
“Combinatorics is an honest subject. No adèles, no sigma-algebras. You count balls in a box, and you either have the right number or you haven’t. You get the feeling that the result you have discovered is forever, because it’s concrete. Other branches of mathematics are not so clear-cut. Functional analysis of infinite-dimensional spaces is never fully convincing; you don’t get a feeling of having done an honest day’s work. Don’t get the wrong idea – combinatorics is not just putting balls into boxes. Counting finite sets can be a highbrow undertaking, with sophisticated techniques.
[…]
Much combinatorics of our day came out of an extraordinary coincidence. Disparate problems in combinatorics, ranging from problems in statistical mechanics to the problem of coloring a map, seem to bear no common features. However, they do have at least one common feature: their solution can be reduced to the problem of finding the roots of some polynomial or analytic function. The minimum number of colors required to properly color a map is given by the roots of a polynomial, called the chromatic polynomial; its value at N tells you in how many ways you can color the map with N colors. Similarly, the singularities of some complicated analytic function tell you the temperature at which a phase transition occurs in matter. The great insight, which is a long way from being understood, was to realize that the roots of the polynomials and analytic functions arising in a lot of combinatorial problems are the Betti numbers of certain surfaces related to the problem. Roughly speaking, the Betti numbers of a surface describe the number of different ways you can go around it. We are now trying to understand how this extraordinary coincidence comes about. If we do, we will have found a notable unification in mathematics.”
________________
*While having an axe to grind is a fairly common phrase. I got the idea of using it from an amazon review of Indiscrete thoughts (check link above). Because I really do think that that is the best description for a lot of his writings!

## 1966 Film on John von Neumann

John von Neumann made so many fundamental contributions that Paul Halmos remarked that it was almost like von Neumann maintained a list of various subjects that he wanted to touch and develop and he systematically kept ticking items off. This sounds to be remarkably true if one just has a glance at the dizzyingly long “known for” column below his photograph on his wikipedia entry.

John von Neumann with one of his computers.

Since Neumann died (young) in 1957, rather unfortunately, there aren’t very many audio/video recordings of his (if I am correct just one 2 minute video recording exists in the public domain so far).

I recently came across a fantastic film on him that I would very highly recommend. Although it is old and the audio quality is not the best, it is certainly worth spending an hour on. The fact that this film features Eugene Wigner, Stanislaw UlamOskar Morgenstern, Paul Halmos (whose little presentation I really enjoyed), Herman Goldstein, Hans Bethe and Edward Teller (who I heard for the first time, spoke quite interestingly) alone makes it worthwhile.

Update: The following youtube links have been removed for breach of copyright. The producer of the film David Hoffman, tells us that the movie should be available as a DVD for purchase soon. Please check the comments to this post for more information.

Part 1

Find Part 2 here.

________________

Onionesque Reality Home >>

## Ramanujan: Letters from an Indian Clerk (1987)

I have never done anything useful. No discovery of mine has made or is likely to make, directly or indirectly, for good or for ill, the least difference to the amenity of the world. Judged by all practical standards, the value of my mathematical life is nil. And outside mathematics it is trivial anyhow. The case for my life then, or for anyone else who has been a mathematician in the same sense that I have been one is this: That I have added something to knowledge and helped others to add more, and that these somethings have a value that differ in degree only and not in kind from that of the creations of the great mathematicians or any of the other artists, great or small who’ve left some kind of memorial behind them.

I still say to myself when I am depressed and and find myself forced to listen to pompous and tiresome people “Well, I have done one thing you could never have done, and that is to have collaborated with Littlewood and Ramanujan on something like equal terms.” — G. H. Hardy (A Mathematician’s Apology)

Yesterday I  discovered an old (1987) British documentary on Srinivasa Ramanujan, which was pretty recently uploaded. I was not surprised to see that the video was made available by Christopher J. Sykes, who has been uploading older documentaries (including those by himself) on youtube (For example – The delightful “Richard Feynman and the Quest for Tannu Tuva” was uploaded by him as well. I blogged about it a couple of years ago!). Thanks Chris for these gems!

Since the documentary is pretty old, it is a little slow. But if you have one hour to spare, you should watch it! It features his (now late) widow, a quite young Béla Bollobás and the late Nobel Laureate Subrahmanyan Chandrasekhar. The video is embedded below – in case of any issues also find it linked here.

________________

[Ramanujan: Letters from an Indian Clerk]

________________

I could have written something on Ramanujan, but decided against it. Instead, I’d close this post with an excerpt from a wonderful essay by Freeman Dyson on Ramanujan published in Ramanujan: Essays and Surveys by Berndt and Rankin

Ramanujan: Essays and Surveys (click on image to view on Amazon)

A Walk Through Ramanujan’s Garden — F. J. Dyson

[…] The inequalities (8), (9) and (10) were undoubtedly true, but I had no idea how to prove them in 1942. In the end I just gave up trying to prove them and published them as conjectures in our student magazine “Eureka”. Since there was half a page left over at the end of my paper, they put in a poem by my friend Alison Falconer who was also a poet and mathematician. […]

Short Vision

Thought is the only way that leads to life.

All else is hollow spheres

Reflecting back

In heavy imitation

And blurred degeneration

A senseless image of our world of thought.

.

Man thinks he is the thought which gives him life.

He binds a sheaf and claims it as himself.

He is a ring through which we pass swinging ropes

Which merely move a little as he slips.

.

The Ropes are Thought.

The Space is Time.

Could he but see, then he might climb.

________________

Onionesque Reality Home >>

## The Opinions of Doron Zeilberger

I presume that a lot of people who drop by this blog are familiar with Doron Zeilberger‘s opinions already. Even though a lot of people who know me personally get linked frequently to some or the other opinions of Zeilberger, I thought it would be a good idea to blog about them in any case, for I believe more people should know about them, even if the number is not high enough.

For a one line introduction, Doron Zeilberger is a noted Israeli mathematician who is presently a professor at Rutgers. He maintains a “blog” which has the title “Dr. Z’s Opinions” in which there are an assortment of views on topics broadly related to Mathematics. Zeilberger certainly has a flair for writing and oftentimes makes hard-hitting points which might outrage many (his latest writing on Turing for example is sure to make many people shake their heads in disagreement – me included) which usually could be seen as chipping away at commonly held opinions. All the interestingness about his opinions aside, his sense of humour makes them entertaining in any case. Even if one disagrees with them I would highly recommend them as long as one exercises some discretion in sifting through these Indiscrete Thoughts.

I found his opinions many years ago while searching for something witty about weekly colloquiums which I could send to some of my colleagues who somehow took pride in not going for them. Skipping colloquiums is a habit that I have not understood well. He wrote the following about it (Opinion 20):

Socrates said that one should always marry. If your spouse would turn out to be nice, then you’ll be a happy person. If your spouse would turn out to be a bitch/bastard, then you’ll become a philosopher.

The same thing can be said about the weekly colloquium. If the speaker is good, you’ll learn something new and interesting, usually outside your field. If the speaker is bad, you’ll feel that you have accomplished something painful, like fasting, or running a marathon, so while you may suffer during the talk, you’ll feel much better after it.

What prompted me to blog about his “blog” was a recent opinion of his. Some months ago when Endre Szemeredi won the Abel Prize, I got very excited, almost like a school boy and the next morning I went to the college library to see what the national dailies had to say about the achievement. To my surprise and dismay none of the dailies seem to have noticed it at all! Three or four days after that the New York Times carried a full page advertisement by Rutgers University having a great photo of Szemeredi, however that doesn’t count as news. I was delighted to see that Doron Zeilberger noticed this too and wrote about it (see his 122nd Opinion)

Let me conclude by wishing Endre, “the computer science professor who never touched a computer”, many more beautiful and deep theorems, and console him (and us) that in a hundred years, and definitely in a thousand years, he would be remembered much more than any contemporary sports or movie star, and probably more than any living Nobel prize winner.

One of my all time favourite opinions of his is Opinion 62, which compares the opposing styles of genius of two men I have had the highest respect for – Israel Gelfand and Alexander Grothendieck. I often send it to people who I think are highly scientifically talented but somehow waste time in expending energy in useless causes than trying to do science (especially if one doesn’t have an intellect comparable to some fraction of Grothendieck’s)! I take the liberty of reproducing the entire opinion here –

I just finished reading Allyn Jackson’s fascinating two-part article about the great mathematical genius Alexandre Grothendieck (that appeared in the Notices of the Amer. Math. Soc.) , and Pierre Cartier’s extremely moving and deep essay `Une pays dont on ne conaitrait que le nom: Le “motifs” de Grothendieck’. (that appeared in the very interesting collection “Le Reel en mathematiques”, edited by P. Cartier and Nathalie Charraud, and that represents the proceedings of a conference about psychoanalysis and math).

In Pierre Cartier’s article, in addition to an attempt at a penetrating “psychoanalysis” he also gives a very lucid non-technical summary of Grothendieck’s mathematical contributions. From this it is clear that one of the greatest giants on whose shoulders Grothendieck stood was Israel Gelfand, whom I am very fortunate to know personally (I am one of the few (too few!) regulars that attend his weekly seminar at Rutgers). I couldn’t help notice the great contrast between these two Giants, and their opposing styles of Genius.

Myself, I am not even an amateaur psychoanalyst, but motives and psi aside, I can easily explain why Grothendieck stopped doing math a long time ago (hence, died, according to Erdos’s nomenclature), while Gelfand, at age 91, is as active and creative as ever.

First and foremost, Grothendieck is a dogmatic purist (like many of the Bourbakists). He dislikes any influences from outside mathematics, or even from other subareas of math. In particular, he always abhored mathematical physics. Ironically, as Cartier explains so well, many major applications of his ground-breaking work were achieved by interfacing it with mathematical physics, in the hands of the “Russian” school, all of whom were disciples of Gelfand. As for Combinatorics, forget it! And don’t even mention the computer, it is du diable. As for Gelfand, he was always sympathetic to all science, even biology! In fact he is also considered a prominent theoretical biologist. Gelfand also realizes the importance of combinatorics and computers.

Also people. Grothendieck was a loner, and hardly collaborated. On the other hand, Gelfand always (at least in the last sixty years) works with other people. Gelfand is also very interested in pedagogy, and in establishing math as an adequate language.

Grothendieck spent a lot of energy in rebellious political causes, probably since in his youth he was an obedient bon eleve. On the other hand, Gelfand was already kicked out of high-school (for political reasons), so could focus all his rebellious energy on innovative math.

So even if you are not quite as smart or original as Gelfand and Grothendieck (and who is?), you will still be able to do math well into your nineties, if you follow Gelfand’s, rather than Grothendieck’s, example.

Zeilberger also seems to have a lot of respect for G. J. Chaitin, something that I certainly find very interesting. I mention this because I have been reading and re-reading Chaitin these days, especially after discovering some of his very recent work on meta-biology.

PS: Zeilgerber was featured in a BBC Documentary on infinity (not a great one, though) in which he talked about his ultrafinitist viewpoint.

________________

Onionesque Reality Home >>

## Endre Szemerédi wins the Abel Prize

In absolutely big news, the Norwegian Academy of Science and Letters has made a fantastic decision by awarding the 2012 Abel Prize to Prof. Endre Szemeredi, one of the greatest mathematicians of our time. We must remember that such decisions are made by committees, and hence I would congratulate the Abel Committee (comprising of Ragni Piene, Terence Tao, Dave Donoho, M. S. Raghunathan and Noga Alon) for such an excellent decision !

Some months ago I told one of my über-cool-dude supervisors (Gabor) that Endre would win the Abel prize this year (guessing was no rocket science!)! I usually don’t like making such statements as there are always many great mathematicians who could win at any given time and there are a lot of other factors too. But Gabor actually told this to Endre, who ofcourse didn’t think it was serious. But apparently he did win it this year! A very well deserved award!

It’s pointless to make an attempt to talk about (not that I am competent to do so anyway) some of Prof. Szemeredi’s deep results and the resulting fundamental contributions to mathematics. Timothy Gowers wrote a good article on the same for the non-mathematical audience. Especially see a mention of Machine Learning on page 7. However, other than the Regularity Lemma that I find absolutely beautiful, my other favorite result of Szemeredi is his Crossing Lemma. A brief discussion on the Regularity Lemma in an older blog post can be found here.

An Irregular Mind: Szemeredi is 70. Book from Szemeredi’s 70th birthday conference recently.

For a short background Prof. Szemeredi was born in Budapest and initially studied at Eötvös before getting his PhD from Moscow State University, where he was advised by the legendary Soviet mathematician Israel Gelfand. He presently holds a position both at the Alfréd Rényi Institute of Mathematics and Rutgers and has had held visiting positions at numerous other places. Recently on his 70th birthday The János Bolyai Mathematical Society organized a conference in his honour, the proceedings of which were published as an appropriately titled book – “An Irregular Mind” (obviously a play on his “Regularity Lemma” and related work and as stated in the book “Szemerédi has an ‘irregular mind’; his brain is wired differently than for most mathematicians. Many of us admire his unique way of thinking, his extraordinary vision.”).

Congratulations to Endre Szemeredi and the great, absolutely unique Hungarian way of doing mathematics.

_________________________

See Also: Short Course on Additive Combinatorics focused on the Regularity Lemma and Szemeredi’s Theorem, Princeton University. (h/t Ayan Acharya)

Onionesque Reality Home >>


text:
2013
12-04

Arbitrage

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

The input file will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Case 1: Yes
Case 2: No

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define re(i,n) for(int i=0;i<n;i++)
#define re1(i,n) for(int i=1;i<=n;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf (1<<29)
const int maxn =33;
int n , m;
double G[maxn][maxn] , diss;
char ch[maxn][maxn] , ch1[maxn] , ch2[maxn];
void floyd() {
re(k,n) re(i,n) re(j,n) if(G[i][j] < G[i][k]*G[k][j])
G[i][j] = G[i][k] * G[k][j];
}
int main() {
int cas = 1;
while(~scanf("%d",&n) && n) {
clr(G,0);
re(i,n) scanf("%s",ch[i]);
scanf("%d",&m);
while(m--) {
int u , v;
scanf("%s%lf%s",ch1,&diss,ch2);
re(i,n) if(strcmp(ch[i],ch1) == 0) { u = i; break; }
re(i,n) if(strcmp(ch[i],ch2) == 0) { v = i; break; }
G[u][v] = diss;
}
floyd();
int flag = 0;
re(i,n) if(G[i][i] > 1) { flag = 1; break; }
if(flag) printf("Case %d: Yes\n",cas++);
else printf("Case %d: No\n",cas++);
}
return 0;
}

1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

2. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.


text:
# We have two particles A and B flying with different speed. Now the rest frame for A

We have two particles $A$ and $B$ flying with different speed. Now the rest frame for $A$ and $B$ is not the same. But is the inertial frame the same? Or would be the inertial frame the same if we have a third fix point $C$ and we would observe them both from $C$?
For me it seems logical to have $3$ frame of references. From the point of view of $A$, from the point of view of $B$ and from an independent point of view $C$. Is this correct?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Mollie Roberts
You write about the rest frame and the inertial frame, but there are infinitely many such frames. The more dimensions we have, the more possibilities. Even with only 1 dimension, frames can differ in the position of their origin, in their speed, their acceleration, and higher rates of change of position.
A "rest frame" is one in which a particular object is at rest. Unless we are restricted to motion in 1 dimension, its axes can point in any direction, so there is not one "rest frame" for each object.
An "inertial reference frame" is one in which Newton's Laws of motion are true : in particular, an object not acted on by any forces remains at rest or moves in a straight line with constant speed. Any reference frame which is moving with constant velocity relative to an inertial reference frame is also an inertial reference frame.
A "rest frame" will not be an "inertial frame" if the object is accelerating, which includes rotating in a circle or spinning on its axis.
It is not clear what you are asking in your last paragraph. Even with 3 points or objects, there are infinitely many possible frames of reference.


text:
# Solved papers for JEE Main & Advanced JEE Main Paper (Held On 11 April 2015)

### done JEE Main Paper (Held On 11 April 2015)

• question_answer1) If the lengths of the sides of a triangle are decided by the three throws of a single fair die, then the probability that the triangle is of maximum area given that it is an isosceles triangle, is : [JEE Main Online Paper (Held On 11 April 2015)]

A) $\frac{1}{26}$

B) $\frac{1}{27}$

C) $\frac{1}{21}$

D) $\frac{1}{15}$

• question_answer2) If the mean and the variance of a binomial variate X are 2 and 1 respectively, then the probability that X takes a value greater than or equal to one is : [JEE Main Online Paper (Held On 11 April 2015)]

A) $\frac{1}{16}$

B) $\frac{9}{16}$

C) $\frac{3}{4}$

D) $\frac{15}{16}$