Herng Yi Cheng
  • Home
  • Publications
  • CV
  • Outreach
  • Art
    • Origami >
      • Origami Design Gallery
      • Origami Publications
      • Origami Research and Applications
      • Modular Polyhedra from Waterbomb Base Units
    • Performance
  • Software
    • Featured Project
  • Blog
    • Featured Post
  • Links

Analogies between finitary and infinitary math

5/20/2013

0 Comments

 
Part 5 of a six-part series of adaptations from Terence Tao’s book “Structure and Randomness".

Prerequisites

Readers need some familiarity with sentences like "for every $\varepsilon$ there exists a large $N$ such that..." or its symbolic equivalent, "$\forall\varepsilon: \exists N: \dotsc$".

A rough idea of big O notation would also be helpful but is not necessary. A brief introduction: we say that $f(x) = O(g(x))$ (as $x \to \infty$) to mean that the "growth" of $f(x)$ is "bounded above" by $g(x)$; more formally, there exist positive real numbers $M$ and $x_0$ such that $\lvert f(x)\rvert \leq M\lvert g(x)\rvert$ for all $x > x_0$.

Note that $\lvert x\rvert$ denotes the absolute value of $x$, not its cardinality as indicated in Part 4.

[1.3] Soft analysis, hard analysis, and the finite convergence principle

Analysis (something like an advanced calculus) is often differentiated into "hard analysis" ("quantitative", "finitary") and "soft analysis" ("qualitative", "infinitary"). Discrete math, computer science, and analytic  number theory normally uses hard analysis while operator algebra, abstract harmonic analysis, and ergodic theory tend to rely on soft analysis. The field of partial differential equations uses techniques from both.

Convenient notation (e.g. $O(\:)$) from qualitative analysis can conceal gritty details from quantitative and argue efficiently from the big picture, at the cost of a precise description. Conversely, quantitative analysis can be seen as a more precise and detailed refinement of qualitative analysis. The intuitions, methods and results in hard analysis often have analogues in soft analysis and vice versa, despite their contrasting language. Tao argues this technique transfer can benefit both disciplines. Table 5 features a rough "dictionary" between the notational languages of soft and hard analysis. Kudos to Tao for such an illuminating comparison!
Table 5: "Translating" soft analysis to hard analysis [1.3]
Soft analysis Hard analysis
$x$ is finite $x$ is bounded (e.g. $x = O(1)$)
$x$ vanishes $x$ is small (e.g. $\lvert x\rvert \leq \varepsilon$)
$x$ is infinite $x$ is large (e.g. $\lvert x\rvert \geq N$)
$x_n \to 0$ Quantitative decay bound (e.g. $x_n = O(n^{-c})$)
$x_n$ is convergent $x_n$ is metastable*

Read More
0 Comments

Drawing networks on a plane

5/16/2013

0 Comments

 
Part 4 of a six-part series of adaptations from Terence Tao’s book “Structure and Randomness".

[1.10] The crossing number inequality

A graph $G = (V, E)$ is a set $V$ of vertices ("objects") and a set $E$ of edges ("relationships between two objects"). For example, $V$ could be a set of people and $E$ the set of friendships (Facebook really uses this social graph to analyze user behavior). $V$ could also be the set of airports and $E$ the set of flights from one airport to another. The immense flexibility of this definition allow graphs to model and analyze a tremendous variety of real-life situations, but here we are interested in the abstract representation of a graph, in particular its drawing. The focus is on applying the technique of amplification, which was presented in Part 3 of this series.

A drawing of graph $G = (V, E)$ simply draws the vertices in $V$ as dots on the plane, and the edges $E$ as lines (or curves) connecting them. $G$ can have many possible drawings, in which the edges can have different numbers of crossings between pairs of edges (i.e. three concurrent edges have 3 crossings). Fig. 4(a)-(c) features three drawings of the $K_{3, 3}$ graph with different numbers of crossings.
Finding the crossing number of the K_{3, 3} graph by twiddling its diagram to reduce crossings
Figure 4: Drawings of K_{3, 3}. Vertices can be moved around to reduce the number of edge crossings (red circles). (a) The usual drawing has 9 crossings. (b) Reduction to 3 crossings. (c) 1 crossing is the minimum.

Read More
0 Comments

Strengthening inequalities: a mathematical trick

5/13/2013

0 Comments

 
Part 3 of a six-part series of summaries and adaptations from Terence Tao's book "Structure and Randomness".

[1.9] Amplification, arbitrage, and the tensor power trick

Given an inequality $f(x) \leq g(x)$ with imbalances in symmetry between the left-hand side (LHS) and right-hand side (RHS), amplification is a mathematical trick that can exploit that imbalance to derive a stronger inequality (i.e. the LHS and RHS are closer). As for why mathematicians might need such a technique, see "Why do we need strong inequalities?" below.

Consider some transformations $T$ that change $x$ such that $g$, but not $f$, is "symmetric" relative to $T$. That is, $f(T(x)) \leq g(T(x)) = g(x)$. Then we can choose $T$ to maximize the LHS $f(T(x))$ and "tighten" the inequality. Let's illustrate this trick by applying it to prove the Cauchy-Schwarz Inequality (actually, the special case of the familiar $n$-dimensional space $\mathbb{R}^n$):
$$\lvert\mathbf{v} \cdot \mathbf{w}\rvert \leq \lVert\mathbf{v}\rVert\lVert\mathbf{w}\rVert \text{ for all } \mathbf{v}, \mathbf{w} \in \mathbb{R}^n \tag{3.1}$$

Read More
0 Comments

Image compression basics

5/12/2013

0 Comments

 
Part 2 of a six-part series of adaptations from Terence Tao’s book “Structure and Randomness".

[1.2] Compressed sensing and single-pixel cameras

This'll be quick; the only part of the original blog post that I understood comfortably was the brief (and slightly inaccurate) explanation of traditional image compression. It's how image formats like JPEG can reduce the memory space needed by an image file drastically while losing only a bit of quality.
Before image compression and after image compression. The data savings far outweigh the slight drop in quality.
The data savings far outweigh the quality loss. Research is ongoing to minimize quality loss without using more storage space.

Read More
0 Comments

Tomb raider: an analogy for quantum weirdness

5/11/2013

0 Comments

 
Part 1 of a six-part series of adaptations from Terence Tao’s book “Structure and Randomness".

[1.1] Quantum mechanics and Tomb Raider

Tao uses the analogy of the game Tomb Raider as a model to give some intuition for the reasons behind the "weird" consequences of quantum mechanics (QM), in particular the so-called "many worlds interpretation". The game consists of two worlds:

  • Internal System: Lara Croft, the protagonist, needs to navigate tombs and solve the puzzles in them to survive. Suppose that she is intelligent and independent of the Player of the game.
  • External System: the Player of the game can view the game world and "save" the game to "restore" it when Lara dies. "Restoring" resets Lara's memory (well, she simply went back to an "earlier state", right?). Unfortunately, he cannot see inside the tombs, which limits his assistance.

(At this point, Tao apologizes for the violent analogy. Well, I've added a little drama... and fixed a loophole.)

Each save point before a lethal puzzle causes Lara's world (from her point of view) to split into many possible "developments",  some of which involve her failure to solve the puzzle and thus death, while others have her survive. Figure 1 illustrates a sample puzzle: A tomb whose only exit a wooden trapdoor on the floor that leads to an underground passage. The tomb will collapse in, say, five minutes, and Lara ("L") must escape through the passageway, but the trapdoor is locked. The Player (smiley face) helps by creating a save point.
Tomb Raider as an analogy for Quantum Mechanics. The three tries it takes for Lara Croft (L) to survive a puzzle cause a split into many timelines.
Figure 1(a): Playing out a puzzle in a cave. The Player (smiley face) creates a save point to give Lara Croft ("L") three attempts to clear the puzzle; she only survives the last attempt.

Read More
0 Comments

Bird's-eye views of Structure and Randomness (Series)

5/3/2013

1 Comment

 
The first posts that I read from Fields Medalist Terence Tao's research blog "What's new" were pieces of advice to aspiring mathematicians, such as mathematical writing tips or what it takes to do math. His blog helped me decide to create my own blog to talk about my own math research, among other things. But his technical posts put me off reading his blog until I recently read a compilation of some of his posts in his book Structure and Randomness (Tao, 2008) (See cover at right).

His expository articles on math and science were surprisingly nontechnical, as well as fun and enriching to read. They conveyed the big picture of the topics in question, imparting an intuition and wonder of the way that math and mathematicians work. I could understand only a few articles, but even so I decided to share my joy with other nontechnical readers like myself. I have extracted what I could understand, expanded on it and adapted it to minimize prerequisite math knowledge, into the following six-part article series:
Structure and Randomness, the book version of Terence Tao's mathematical blog. A compilation of several expository articles, lectures and open problems.
Expository articles, lectures and open problems.

Read More
1 Comment

    Archives

    December 2020
    February 2020
    January 2019
    December 2018
    May 2018
    December 2017
    August 2017
    July 2017
    May 2016
    October 2015
    December 2014
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    February 2014
    January 2014
    September 2013
    June 2013
    May 2013
    March 2013
    December 2012

    RSS Feed

    Categories

    All
    Advocacy
    Art
    Design
    Elementary
    Exhibition
    Mathematics
    MIT
    Musing
    Origami
    Programming
    Puzzle
    Research
    Science
    Teaching
    Theater
    Writing

  • Home
  • Publications
  • CV
  • Outreach
  • Art
    • Origami >
      • Origami Design Gallery
      • Origami Publications
      • Origami Research and Applications
      • Modular Polyhedra from Waterbomb Base Units
    • Performance
  • Software
    • Featured Project
  • Blog
    • Featured Post
  • Links