ALGEBRA

Titu’s Lemma (Also known as Engel’s Inequality)

🔹 Statement:

For positive real numbers a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​ and b1,b2,…,bnb_1, b_2, \ldots, b_nb1​,b2​,…,bn​ with bi>0b_i > 0bi​>0, the following holds:

a12b1+a22b2+⋯+an2bn≥(a1+a2+⋯+an)2b1+b2+⋯+bn\frac{a_1^2}{b_1} + \frac{a_2^2}{b_2} + \cdots + \frac{a_n^2}{b_n} \geq \frac{(a_1 + a_2 + \cdots + a_n)^2}{b_1 + b_2 + \cdots + b_n}b1​a12​​+b2​a22​​+⋯+bn​an2​​≥b1​+b2​+⋯+bn​(a1​+a2​+⋯+an​)2​

🔎 When to Use Titu’s Lemma

• You see a sum of fractions like ∑x2a\sum \frac{x^2}{a}∑ax2​, ∑a2x\sum \frac{a^2}{x}∑xa2​, etc.
  
  

• You're asked to prove a lower bound for such a sum.
  
  

• The expressions suggest an application of Cauchy-Schwarz Inequality in disguise.
  
  

Derivation from Cauchy-Schwarz

Apply Cauchy-Schwarz on sequences:

(∑ai2bi)(∑bi)≥(∑ai)2\left( \sum \frac{a_i^2}{b_i} \right)\left( \sum b_i \right) \geq \left( \sum a_i \right)^2(∑bi​ai2​​)(∑bi​)≥(∑ai​)2

Divide both sides by ∑bi\sum b_i∑bi​, and you get Titu’s Lemma.

✅ Examples

Example 1:

Let a,b,c>0a, b, c > 0a,b,c>0. Prove:

a2b+b2c+c2a≥(a+b+c)2a+b+c\frac{a^2}{b} + \frac{b^2}{c} + \frac{c^2}{a} \geq \frac{(a + b + c)^2}{a + b + c}ba2​+cb2​+ac2​≥a+b+c(a+b+c)2​

Solution:
Apply Titu’s Lemma:

a2b+b2c+c2a≥(a+b+c)2a+b+c=a+b+c\frac{a^2}{b} + \frac{b^2}{c} + \frac{c^2}{a} \geq \frac{(a + b + c)^2}{a + b + c} = a + b + cba2​+cb2​+ac2​≥a+b+c(a+b+c)2​=a+b+c 

vSo,

a2b+b2c+c2a≥a+b+c\frac{a^2}{b} + \frac{b^2}{c} + \frac{c^2}{a} \geq a + b + cba2​+cb2​+ac2​≥a+b+c

✔️ Proven.

Example 2:

Prove that for x,y,z>0x, y, z > 0x,y,z>0,

x2y+z+y2z+x+z2x+y≥x+y+z2\frac{x^2}{y+z} + \frac{y^2}{z+x} + \frac{z^2}{x+y} \geq \frac{x + y + z}{2}y+zx2​+z+xy2​+x+yz2​≥2x+y+z​

Solution:
Use Titu’s Lemma:

∑x2y+z≥(x+y+z)22(x+y+z)=x+y+z2\sum \frac{x^2}{y+z} \geq \frac{(x + y + z)^2}{2(x + y + z)} = \frac{x + y + z}{2}∑y+zx2​≥2(x+y+z)(x+y+z)2​=2x+y+z​

✔️ Done.

⚠️ Common Mistakes

• Using it when numerators aren't squares (e.g., ab\frac{a}{b}ba​) — doesn’t apply directly.
  
  

• Using it when bib_ibi​ are zero or negative — invalid.

What is a Coordinate Ring?

The coordinate ring of an algebraic variety is the ring of polynomial functions defined on it.

More formally:

🔹 For an affine variety V⊂AnV \subset \mathbb{A}^nV⊂An (usually over R\mathbb{R}R or C\mathbb{C}C), defined as the set of common zeros of a set of polynomials {f1,…,fk}∈F[x1,…,xn]\{f_1, \ldots, f_k\} \in \mathbb{F}[x_1, \ldots, x_n]{f1​,…,fk​}∈F[x1​,…,xn​], the coordinate ring is:

F[x1,x2,…,xn]/I(V)\mathbb{F}[x_1, x_2, \ldots, x_n]/I(V)F[x1​,x2​,…,xn​]/I(V)

Where:

• F[x1,…,xn]\mathbb{F}[x_1, \ldots, x_n]F[x1​,…,xn​] is the ring of polynomials over a field F\mathbb{F}F,
  
  

• I(V)I(V)I(V) is the ideal of polynomials vanishing on VVV (i.e., all polynomials that are zero on every point of VVV).
  
  

✅ Example 1: A Line in A2\mathbb{A}^2A2

Let’s say we have a line:

V={(x,y)∈R2∣y−x=0}V = \{(x, y) \in \mathbb{R}^2 \mid y - x = 0\}V={(x,y)∈R2∣y−x=0}

So this is the set of all points where y=xy = xy=x. The ideal defining this is:

I=(y−x)⊂R[x,y]I = (y - x) \subset \mathbb{R}[x, y]I=(y−x)⊂R[x,y]

Then the coordinate ring is:

R[x,y]/(y−x)

This means we treat yyy as equal to xxx in all polynomials, so effectively:

R[x,y]/(y−x)≅R[x]\mathbb{R}[x, y]/(y - x) \cong \mathbb{R}[x]R[x,y]/(y−x)≅R[x]

✔️ Intuitively, this says that functions on the line y=xy = xy=x can be fully described using just one variable.

✅ Example 2: The Circle x2+y2=1x^2 + y^2 = 1x2+y2=1

Let:

V={(x,y)∈R2∣x2+y2−1=0}V = \{(x, y) \in \mathbb{R}^2 \mid x^2 + y^2 - 1 = 0\}V={(x,y)∈R2∣x2+y2−1=0}

The coordinate ring is:

R[x,y]/(x2+y2−1)\mathbb{R}[x, y]/(x^2 + y^2 - 1)R[x,y]/(x2+y2−1)

This ring contains all polynomial expressions in xxx and yyy, modulo the relation x2+y2=1x^2 + y^2 = 1x2+y2=1.

That means:

• If a polynomial contains x2x^2x2, we can replace it using the identity x2=1−y2x^2 = 1 - y^2x2=1−y2, and vice versa

Chinese Remainder Theorem (CRT) – Core Idea

The CRT tells us:

If you have multiple congruences with pairwise coprime moduli, then there exists a unique solution modulo the product of those moduli.

🔹 Formal Statement

Let m1,m2,…,mkm_1, m_2, \ldots, m_km1​,m2​,…,mk​ be pairwise coprime positive integers (i.e., gcd⁡(mi,mj)=1\gcd(m_i, m_j) = 1gcd(mi​,mj​)=1 for i≠ji \ne ji=j).

Let a1,a2,…,aka_1, a_2, \ldots, a_ka1​,a2​,…,ak​ be any integers.

Then, the system of congruences:

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}⎩⎨⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡ak​(modmk​)​

has a unique solution modulo M=m1m2⋯mkM = m_1 m_2 \cdots m_kM=m1​m2​⋯mk​.

That is, there exists one value of xmod  Mx \mod MxmodM satisfying all congruences.

Step-by-Step Construction (2 Congruences)

Let’s work with:

{x≡a1(modm1)x≡a2(modm2)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases}{x≡a1​(modm1​)x≡a2​(modm2​)​

where gcd⁡(m1,m2)=1\gcd(m_1, m_2) = 1gcd(m1​,m2​)=1

Let’s find a solution.

✅ Example:

Solve:

{x≡2(mod3)x≡3(mod5)\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \end{cases}{x≡2(mod3)x≡3(mod5)​

Step 1: Let M=3×5=15M = 3 \times 5 = 15M=3×5=15

We are looking for xxx such that:

• x≡2mod  3x \equiv 2 \mod 3x≡2mod3
  
  

• x≡3mod  5x \equiv 3 \mod 5x≡3mod5

Step 2: Try values of x≡3mod  5x \equiv 3 \mod 5x≡3mod5

The numbers are:

3,8,13,18,23,…3, 8, 13, 18, 23, \ldots3,8,13,18,23,…

Check which of these also satisfies x≡2mod  3x \equiv 2 \mod 3x≡2mod3:

• 3mod  3=03 \mod 3 = 03mod3=0 ❌
  
  

• 8mod  3=28 \mod 3 = 28mod3=2 ✅
  
  

So, x=8x = 8x=8 satisfies both congruences.

✅ Final answer:

x≡8(mod15)x \equiv 8 \pmod{15}x≡8(mod15) 

General CRT Algorithm (with Construction)

Let’s solve:

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}⎩⎨⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡ak​(modmk​)​

Assume all mim_imi​ are pairwise coprime.

Let M=m1m2⋯mkM = m_1 m_2 \cdots m_kM=m1​m2​⋯mk​

For each iii:

• Let Mi=MmiM_i = \frac{M}{m_i}Mi​=mi​M​
  
  

• Find the modular inverse of Mimod  miM_i \mod m_iMi​modmi​: call it yiy_iyi​ so that:
  Mi⋅yi≡1(modmi)M_i \cdot y_i \equiv 1 \pmod{m_i}Mi​⋅yi​≡1(modmi​)

Then the solution is:

x≡∑i=1kai⋅Mi⋅yi(modM)x \equiv \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i \pmod{M}x≡i=1∑k​ai​⋅Mi​⋅yi​(modM)