Notes

Transformational grammar (Chomsky, 1957).

Sentences have

1. Deep structure (closer to semantics): represents the sentence as a tree.
2. Surface structure (language-specific) represents the sentence as a tree after some transformations.

Example 2.8. Consider the sentence

John eats the apple.

1. Deep structure represents the sentence using a tree (imprecise, but bear with this):

2. Transformational grammar equips us with a couple of pre-built transformations that we can use on this tree (passivization, question formation, negation, movement, etc.). The point of these transformations is to produce a list of related sentence-trees and say they are equivalent:

John eats the apple.
The apple was eaten by John.
Did John eat the apple?
Was the apple eaten by John?
⋮

This approach enables us to create tree families that represent the same semantic idea. The tree-representations for each of these are surface structure.

One might ask, “why did we pick John eats the apple as the deep structure tree?” We actually did not; we just made some universal assignments:

and created a tree out of that; it’s just that this tree happened to look like “John eats the apple” when unrolled. The sentence tree itself is surface-level; the deep-level is this abstract assignment tree. So in general,

There are obviously many issues with this. Here are the biggest ones in my opinion:

1. Too many transformations.
2. Transformation rules may not be precise.
3. Multiple hard-coded rules.
4. Messy when dealing with multiple languages, especially because passive transformation rules differ language-to-language.

This motivates the next idea.

Principles and parameters (Chomsky, 1981).

Two components:

1. Principles (general grammar rules). E.g., “when building a grammar you must represent lexical word elements syntactically” (Projection Principle) or “each argument of a phrase gets one role” ($\theta$-criterion). These are true for all languages.
2. Parameters (binary variables distinguishing different languages syntactically).

So universal principles plus language-specific parameter settings compose a specific language’s grammar. If you were to design a new language, you should note this.

Example 2.9. Let’s say “heads before complements” is a parameter. Then, for English (param=1) and Japanese (param=0) respectively, possible trees allowed by the grammar are:

Through P&P, in an idealized world, languages are encoded as bitstrings that represent each parameter, with “general design decisions” enforced through the principles.

Example principles:

• Structure Preservation Principle
• Projection Principle
• Subjacency Principle

Example parameters:

• Head-directionality
• Subject-side
• Pro-drop
• Null-subject
• Word order (SOV, SVO, VSO, VOS, OVS, OSV)

There are a couple problems with P&P:

1. Interdependencies between parameters. Mathematically, an aim is to figure out the “ideal set” of generators, but linguists haven’t found this yet.
2. Changes of parameters as languages evolve (e.g., word order changes in Homeric to Classical Greek, switches from Old English to English, etc.).

What is linguistics?

1. Syntax is the subset of a language’s grammar that has to do with how words legally combine into sentences. (Other subsets include morphology, which deals with how morphemes combine into words, and phonics, which deals with individual unit sounds.)

2. Language is not just a “sequence of words” because some sequences are structurally illegal. Rather, language is a “sequence of words that follows a template, paired with a hierarchy.” The hierarchy is important, as the same word-sequence with different hierarchy can constitute different sentences:

[I saw [the man with the telescope.]]
[I saw [the man][with the telescope.]]

Another example:

I shot an elephant in my pajamas.

The sentence has two possible syntactic structures.

Here, in my pajamas modifies the verb phrase: I was wearing the pajamas when I shot the elephant.

Here, in my pajamas modifies the noun phrase an elephant: the elephant is in my pajamas.

3. Language can be viewed as a “structure” because it is hierarchically composable. On the morpheme-level, consider:

(un-(friend)-ly))-ness

or as a tree,

These trees can be further composed to give a tree structure on the whole sentence.

4. An i-language is a set of internal grammatical rules in each person’s mind. Thus, i-languages for e.g. English differ person-to-person. There is some intuitive sense of “this sentence feels right” (grammaticality) that each person has based on their specific i-language.

5. There might be some math involved in linguistics; namely, operators defined on the language-trees.

Generative linguistics: formal languages.

Formal languages describe strings of words recognizable by varying classes of automata (called Chomsky hierarchy).

Structures that give rise to formal languages:

• Programming languages
• Some discrete group presentations

The question: which classes of automata can recognize natural languages? A grammar is a quadruple

where

• $V_N$ and $V_T$ are disjoint finite sets: non-terminal and terminal symbols, respectively.
• $S \in V_N$ is the start symbol.
• $P$ is the set of production rules, acting as a finite rewriting system on $V_N \cup V_T$.

The language produced by a grammar $\mathcal{G}$ is given by

Example 2.1. Consider grammar $\mathcal{G} = (\{S, A\}, \{a, b\}, P, S)$ with productions:

Note that a possible word in $L_{\mathcal{G}}$ is given by $abaaa$, since

The Chomsky hierarchy.

Type 0: unrestricted grammar, recognizable by Turing machine. Production rules are general: $\alpha \to \beta$.

Type 1: Context-sensitive grammar, recognizable by linear bounded automaton. A context-sensitive grammar is one with

Note that the context is fixed and just the middle part is re-written. Type 1 is a more restricted version of Type 0.

Type 2: Context-free grammar, recognizable by nondeterministic pushdown automata. Special case of context-sensitive, with $\beta = \gamma = \varepsilon$.

Type 3: Regular grammar, recognizable by finite state automata (e.g., NFA, DFA). More restricted version of Type 2 (we’ll see why in the next example).

Generally, we find that

in terms of expressive power.

Example 2.2 (Context-sensitive grammar). Consider the context-sensitive grammar $\mathcal{G} = (\{S, B, C\}, \{a, b, c\}, P, S)$, with production rules

Then, we find possible strings are

• $S \Rightarrow aBC \Rightarrow abC \Rightarrow abc$
• $S \Rightarrow aSBC \Rightarrow aaBCBC \Rightarrow aabCBC \Rightarrow aabBCC \Rightarrow aabbCC \Rightarrow aabbcC \Rightarrow aabbcc$

and in general,

Example 2.3 (Context-free grammar). Take the context-free grammar $\mathcal{G} = (\{S\}, \{0, 1\}, P, S)$ where the production rules are given by

Then, we find possible strings are

• $01$
• $0011$
• $000111$
• $\ldots$

and in general,

We know this $L_{\mathcal{G}}$ is not regular, because finite automata have fixed memory; remembering $n$ requires storing a variable.

Example 2.4 (Regular grammars). Consider $\mathcal{G} = (\{S, A\}, \{0, 1\}, P, S)$, with production rules

It is clear this is a deterministic finite automaton:

with $A$ as a terminal state. We observe that right-linear production rules yield finite automata, as the nonterminals $\{S, A\}$ can be viewed as states with terminals (or $\varepsilon$) as transitions. This further cements the idea that regular grammars are constrained (right-linear) context-free grammars.

How good are CFGs at representing natural language?

We show not-context-free by highlighting cross-serial dependencies in the language. [Why cross-serial dependencies yield context-free grammars?]

Some examples of context-sensitive languages:

• Dutch.
• Swiss-German. Some legal sentences are of the form

for example, “Jan säit das mer (d’chind)$^n$ (em Hans)$^m$ es huus hälfed wele (laa)$^n$ (hafte)$^m$ aastriiche.”

• $L_{\mathcal{G}} = \{x x^R : x \in \{a, b\}^{\star}\}$ (where $x^R$ is the reversal of $x$).

However, in general, context-sensitive grammars are overkill for representing natural languages. What is the weakest grammar able to represent natural languages?

Formal languages of finitely presented groups.

Consider a situation where the grammar is a finite group, e.g., $\mathcal{G} = G = \langle X \mid R \rangle$. Then,

Example 2.5. Consider $G = C_3 = \langle a \mid a^3 = 1 \rangle$. Then, $\hat{X} = \{a, a^{-1}\}$, and

Example 2.6. Consider $G = D_8 = \langle r, s \mid r^4 = s^2 = 1, srs = r^{-1} \rangle$. Then, $\hat{X} = \{r, r^3, s\}$, and

What kind of formal languages can be represented by such finite groups? Algebraic properties of $G$ correspond to the properties of $L_G$. Note that:

1. $L_G$ is regular iff $G$ is finite.
2. $L_G$ is context-free iff $G$ has a free subgroup of finite index.

Example 2.7. Take the infinite group $G = SL_2(\mathbb{Z}) = \langle S, T \mid S^4 = I, S^2 = (ST)^3 \rangle$, where

We know $L_G$ is not regular since $G$ is not finite. Consider

Since no combination of $A, B$ equals $I$, it follows that $F_2 = \langle A, B \rangle$ is a free group; since $\det A = \det B = 1$, $F_2 \leq G$.

Next, we define $\Gamma(2)$ as the set of matrices congruent to $I_2 \mod 2$. Since

it follows that $A, B \in \Gamma(2)$.

We define $\pi : SL_2(\mathbb{Z}) \to SL_2(\mathbb{F}_2)$, with $\ker \pi = \Gamma(2)$. By the First Isomorphism Theorem,

so $[SL_2(\mathbb{Z}) : \Gamma(2)] = |SL_2(\mathbb{F}_2)| = 6$. Similarly, since $\Gamma(2) = F_2 \sqcup -IF_2$, $[\Gamma(2) : F_2] = 2$, and $[SL_2(\mathbb{Z}) : F_2] = [SL_2(\mathbb{Z}) : \Gamma(2)][\Gamma(2) : F_2] = (6)(2) = 12$. Since $G$ has a free subgroup $H$ of finite index, $L_G$ is context-free.

This section just shows that there is a nice tie between groups and languages. It doesn’t mean we have to use them over production rules.

Boundaries of Babel problem.

How do we formally characterize the space of natural languages? It is between context-sensitive and context-free. What is the geometry of this space? (Geometry basically means we represent each language as a point, with dimensions such as “head size.”)

We want a formal model to describe natural languages. Formal languages are no longer viewed a good way to model generative syntax.

• They focus on strings rather than structures. Remember that the same string can have different meanings based on the hierarchy. Only focusing on the strings means that the hierarchy information is not generated.
• The production rules get too complicated.
• There are too many languages in the context-sensitive class that are not natural languages.

So, context-sensitive grammar is more powerful about strings, not automatically better about trees.

$t$-reachability, $t$-pebbling number.

Let $G$ be a connected graph, and $r \in V(G)$ be the root with $C$ as a pebble configuration. A vertex $r$ is $t$-reachable under $C$ if there is a sequence of ordinary pebbling moves after which $C(r) \geq t$. Equivalently, $C$ is $t$-fold $r$-solvable. (Notice that 1-reachable is simply $r$-solvable.)

Example 2.1. Consider $G = P_3$, with root $r = v_2$ and all pebbles starting at $v_0$. We recall that moving 1 pebble from $v_0$ to $v_2$ requires 4 initial pebbles. To end with $C(v_2) = 2$, we follow the path:

Generally, we conjecture that from a single pile $v$ at distance $d$ from the root, moving $t$ pebbles to the root requires $C(v) \geq (t)(2^n)$.

Notice that $(n+1)$-reachability implies $n$-reachability.

Definition 2.1. We define $\pi_t(G)$ as the smallest integer $k$ such that every configuration of $k$ pebbles is $t$-fold $r$-solvable for all $r \in V(G)$. Note that $\pi_1(G) = \pi(G)$.

Example 2.2 (Trivial $P_2$ example). We compute $\pi_2(P_2)$. Clearly, $\pi_2(P_2) > 2$ (consider $C = (1, 1)$). Fix $r = v_1$; then, $(3, 0)$ is not 2-fold $r$-solvable, so $\pi_2(P_2) > 3$. Since $(4, 0), (3, 1), (\ast, \geq 2)$ are the remaining configurations and 2-fold $v_2$-solvable, $P_2$ is 2-fold $v_1$-solvable. Reversing the direction generalizes to all of $P_2$. Hence, $\pi_2(P_2) = 4$.

Ordinary graph pebbling.

Graph pebbling (now a famous mathematical game) was originally introduced to solve the Erdős–Lemke conjecture: given an integer sequence $a_1, a_2, \ldots, a_n$, there exists a subsequence whose sum is divisible by $n$, provided

Now, let $G = (V, E)$ be a connected graph.

Definition 1.1 (Configuration). A configuration is an assignment $C : V \to \mathbb{Z}_{\geq 0}$, where $C(v)$ is the number of pebbles placed at vertex $v$.

Definition 1.2 (Pebbling move). A pebbling move from vertex $u$ to an (adjacent) vertex $v$ does two things:

1. $C(u) \mapsto C(u) - 2$
2. $C(v) \mapsto C(v) + 1$

Thus, moving a pebble across an edge has a cost; the total pebbles in $G$ are decreased by 1.

Example 1.1. Consider the path graph $P_3$:

Suppose all pebbles are at $v_0$. To place 1 pebble at $v_1$, we need at least 2 pebbles in $v_0$. To place 1 pebble at $v_2$, we need at least 2 pebbles in $v_1$, and therefore 4 pebbles in $v_0$.

Example 1.2. Consider $P_4$. Defining “arrival” at vertex $v$ as having 1 pebble in $v$, we find:

It seems $2^k$ pebbles are needed to reach $v_k$ (if all pebbles start at $v_0$) for a path graph $P_{k+1}$.

Example 1.3 (Reachability depends on the configuration). Consider $P_3$, with $C(v_0) = 3, C(v_1) = 0, C(v_2) = 0$. $v_2$ is not reachable; $(C(v_0), C(v_1), C(v_2)) = (3, 0, 0) \mapsto (1, 1, 0)$ which is a terminal state.

However, $v_2$ is reachable under $(2, 1, 0) \mapsto (0, 2, 0) \mapsto (0, 0, 1)$. Both configurations have 3 total pebbles. This emphasizes that reachability depends not only on total pebbles in $G$, but the specific configuration.

Definition 1.3 ($r$-solvable). Choose a target vertex $r$, called the root. A configuration $C$ is $r$-solvable when a sequence of pebbling moves puts at least 1 pebble in vertex $r$. E.g., in the previous example, the first configuration was not $v_2$-solvable but it was $v_1$-solvable. Thus solvability depends on the configuration and the chosen root.

Definition 1.4 (Pebbling number). The pebbling number $\pi(G)$ is the smallest integer $k$ such that every configuration of $k$ pebbles $C_k$ is $r$-solvable for all $r \in V(G)$.

Note that to prove $\pi(G) \leq k$, we must prove that every $C_k$ is $r$-solvable $\forall r \in V(G)$, whereas to prove $\pi(G) > k$, we must show there exists a configuration $C_k$ that is not $r$-solvable for some $r \in V(G)$.

Example 1.4 (Computing $\pi(P_3)$). In this example, we explicitly compute $\pi(P_3)$.

Proof. We can immediately establish a lower bound from the previous example; since there exists $C_3 = (3, 0, 0)$ that is not $v_2$-solvable, $\pi(P_3) > 3$.

Because $C_4 = (4, 0, 0)$ can reach $v_2$ (the furthest vertex), it is a reasonable conjecture that $\pi(P_3) = 4$. However, we must confirm that every 4-pebble configuration can reach every root. Starting with $r = v_2$: we know the $(\ast, \ast, \geq 1), (\ast, \geq 2, \ast), (4, 0, 0)$ configurations are $v_2$-solvable. This leaves $(3, 1, 0)$, which is solvable through the sequence $(3, 1, 0) \mapsto (1, 2, 0) \mapsto (1, 0, 1)$. Hence, $P_3$ is $v_2$-solvable. (The same logic applies for $v_0$, which can be viewed as an endpoint by reversing $P_3$.)

Finally, we must check if $P_3$ is $v_1$-solvable. Immediately, we know that $(\geq 2, \ast, \ast), (\ast, \ast, \geq 2), (\ast, \geq 1, \ast)$ are $v_1$-solvable. These cover all possible cases; thus, $P_3$ is $v_1$-solvable.

Hence, $\pi(P_3) = 4$. $\square$

Aim: Design a perspective-based game where:

1. The player initially doesn’t know the rules and must figure them out.
2. If the player knows the rules, the game is trivial.
3. Level $n$ introduces a counterexample to what the player thinks the goal is.

The game is perspective-based because it is possible for the player to possess a sub-par world model (perspective) (i.e., one that only perfectly holds from Level 1 to $i$) and still beat the game. World models are built in varying abstraction hierarchies, as shown in [1]:

This is analogous to Relativity (e.g., the staircase in one orientation is a roof in another).

https://arxiv.org/pdf/2507.12821

Loose thoughts: if a platformer, the game map might be similar to Relativity. What seems like a block in 2D could be a door in 3D; progressing across levels in 2D in a scrolling platformer is in reality walking through doors in a 3D choose your own adventure; the 3D choose your own adventure could have interesting topologies, like a Mobius strip taking you back to the start, but with different mechanics only visible in 3D (so if the player still has a 2D world model, they have to build a fake mod 2 rule that doesn't capture the real universe's mechanics).

Given a rectangular chip die, a set of rectangular macros, fixed pins, and a hypergraph netlist, the program searches for a legal macro placement that minimizes estimated wirelength and overlap, with the heavy cost evaluation on the GPU.

Background. Macro placement is an important problem in chip physical design. In modern chips, large blocks such as SRAMs, analog blocks, accelerators, and IP modules must be placed on a two-dimensional die. The placement has to satisfy geometric constraints, such as keeping macros inside the die and avoiding overlap, while also optimizing objectives such as wirelength, routing congestion, and timing.

Input: a rectangular die, a set of rectangular macros (design blocks), and a set of nets (wires) connecting those macros and fixed pins. For example:

{
  "die": {"width": 1000, "height": 1000},
  "macros": [
    {"name": "m0", "width": 100, "height": 80},
    {"name": "m1", "width": 120, "height": 90}
  ],
  "pins": [
    {"name": "p0", "x": 0, "y": 500}
  ],
  "nets": [
    ["m0", "m1", "p0"]
  ]
}

The goal is to assign each macro an $(x, y)$ location such that the macros do not overlap and the estimated interconnect cost is low. This is well-suited for CUDA because many parts of the placement objective are parallelizable. For example, the half-perimeter wirelength of each net can be computed independently. Also, many simulated annealing chains can be run independently in parallel, allowing the GPU to explore many possible placements at once.

The program first generates an initial random placement. The CPU baseline improves the placement using simulated annealing. Then the CUDA implementation runs many annealing chains in parallel and returns the best placement found.

Computation. Each placement consists of coordinates for $N$ macros $P = \{(x_i, y_i)\}_{i=1}^{N}$ where macro $i$ has width $w_i$ and height $h_i$. The cost function combines wirelength, overlap, and boundary penalties:

The half-perimeter wirelength of a net $n$ is:

The total wirelength is $\operatorname{HPWL}(P) = \sum_{n \in \mathcal{N}} \operatorname{HPWL}(n)$ where $\mathcal{N}$ is the set of nets.

The overlap penalty between two macros $i$ and $j$ can be computed using their rectangle intersection area. If macro $i$ occupies $[x_i, x_i + w_i] \times [y_i, y_i + h_i]$ and macro $j$ occupies $[x_j, x_j + w_j] \times [y_j, y_j + h_j]$, then their overlap area is:

The total overlap penalty is:

The simulated annealing algorithm proposes random moves such as moving one macro to a new location or swapping two macros. If the new placement has cost difference $\Delta C = C(P_{\text{new}}) - C(P_{\text{old}})$, then the move is accepted with probability $p = \min\!\left(1, e^{-\Delta C / T}\right)$ where $T$ is the current temperature.

The CPU version runs a single simulated annealing chain. The CUDA version runs many independent chains in parallel, each starting from a different random initial placement. At the end, the program chooses the best placement among all chains.

Results. Each synthetic benchmark below uses the same SA schedule ($T$ from $100$ to $0.001$, cooling $0.995$, $30{,}000$ moves, seed $42$) and the same random initial placement per size. The CPU baseline runs a single annealing chain; the GPU implementation runs $64$ independent chains and keeps the best.

The GPU pays off once the problem is large enough to amortize kernel-launch and transfer overhead: it is ~2.8× faster at medium and ~3.5× faster at large, while also reaching a slightly lower final cost (more chains explore more of the space). On the tiny 8-macro problem the GPU is slower than the CPU (0.24×) — there isn’t enough work to hide the overhead.

Small benchmark. 8 macros, 20 nets, 1000×1000 die. Both solvers cut the cost ~99% with zero overlap and zero boundary violation.

Medium benchmark. 64 macros, 200 nets, 4000×4000 die.

Large benchmark. 256 macros, 1000 nets, 10000×10000 die.

At medium and large sizes a small residual overlap remains (the penalty keeps it tiny but nonzero); the 8-macro case converges to exactly zero overlap.

[1] Socrates outlines a problem with a god-given absolute piety within a polytheistic religion: are pious things pious because the gods love them, or do the gods love them because they are inherently pious?

• The main framework for the former is divine command theory. Risk: morality becomes arbitrary.
• Frameworks for the latter: moral realism, rationalist ethics, etc. Risk: morality is defined outside of god(s).

[2] Euthyphro’s claims are that 1) Zeus would prosecute his own father for manslaughter, 2) he is the only man who knows what the gods would do (perfect religious knowledge), and 3) Man should aspire to do what God would.

• Socrates’ initial critique against 1) is a pushback on prosecuting one’s family. To this, Euthyphro cites Zeus, who put his father Kronos in bonds for “unjustly swallowing his sons,” and Kronos, who castrated his father Ouranos.
• Socrates finds trouble with 3) as it requires a definition of piety and an agreement on all gods’ actions. See [3].

[3] The present situation is generalized into a debate on piety, which Socrates opens by asking for a simple definition.

• Euthyphro’s initial definition: piety is prosecuting the wrongdoer. Socrates easily refutes this as an example of piety rather than a definition.
• Euthyphro’s revised general definition: what is loved by the gods is pious, and what is not loved by the gods is impious (loved by the gods iff. pious).
• Socrates points out the problem of disagreement on piety within a polytheistic framework, to which Euthyphro claims (see [1]) that on his current matter, the gods reach agreement. This implicitly re-defines piety to “what is loved by ALL gods is pious”, and impiety to “what is hated by ALL gods is impious.”
  • This breaks the biconditional: now, something can be pious without being loved by all the gods (since it no longer falls under the definition of impiety). Similarly, something can be impious without being hated by all the gods.
  • This changes Euthyphro’s “definition” of piety to an example of it (“what is loved by ALL gods” is an example of many things which are pious).
• Socrates asks, “is the pious loved by the gods because it is pious, or is it pious because it is loved by the gods?”
  • (Biconditional can hold; good movie iff. is loved by all critics. However, is it a good movie because it is loved by all critics, or is it loved by all critics because it is a good movie? The latter is more plausible; there exists a deeper reason humans find a movie “good,” and all critics have captured it.)
  • Socrates takes a similar stance: the pious is loved by the gods because it is pious.
• Euthyphro revises piety again: “the part of justice concerned with attending to the gods.”
  • This definition seems to be something loved by all the gods, so it is valid.
  • Socrates refutes: “what can humans give gods that they don’t already have or can get?”
  • (I disagree with Euthyphro’s slavery analogy; because humans are finite, the master puts the slave to work on tasks he does not have time or will for. This does not seem to be the form of “attending” gods would like from humans. Rather, the only thing gods cannot do (self-imposedly) is violate human free will; hence, they require attending in human belief, e.g., prayer, sacrifices, etc.)
    • Still, if piety is sacrifice/prayer that pleases the gods, then Euthyphro has circled back to “pious is what is loved by the gods.”

I had to think about this question a lot when:

1. Moving to California and forfeiting college enrollment.
2. Living alone in Sonoma County, working to prove to parents, friends, VCs, and myself that I was exceptional.
3. Working 16 hour days in Arcadia, ending up in the hospital (treating the people around me poorly; zero tolerance for distractions).
4. Meeting my (former) love; sleepless nights working to afford an immigration lawyer so she wouldn’t have to leave the US.
5. Contemplating various ethical dilemmas in business.
6. Shutting down my second startup.
7. My friend’s death.
8. Quitting my first and second (well-paying) jobs.
9. Giving up my girlfriend’s hand in marriage and coming to Caltech.
10. Watching my ex girlfriend struggle with homelessness, solitude, and suicide; failing to get the New York Police Department to track her down.
11. My grandfather’s death.

My experiences have shaped me into (currently) a firm existentialist. I value:

1. Knowledge and understanding. I want to understand and imagine the mathematical ideas that lie even beyond our observable universe; what can be thought of? What can’t be computed? I want to understand the recursive structure of language; the structure of music, comedy; what is moral, just (how would various philosophers have approached my gap year?); the culty-ness of startups and universities, Girard’s mimetic theory, and organized (political?) (religious?) groups.
2. Being special.
3. Self-improvement. After running my second business for a couple of months I began to feel unstoppable; I was solving challenge after challenge. I know that doesn’t sound unique to business…I can’t explain this properly yet; I’ll add examples when I think of them.
4. Love. My favorite one-liner encapsulating love is ironically from Nietzsche (Beyond Good and Evil, Aphorism 153): “That which is done out of love always takes place beyond good and evil.” 'nuff said. See this.

I used to help out at a VC/accelerator that Sam Altman put money into. My job was to read applications and determine who gets accepted (maybe funded). I saw it as paying back gratitude to something fundamental to my journey: 1) I had participated in it before, and 2) Nick and Aili helped give me a place to live when I was relatively desperate.

I met Sam Altman a couple times but I didn’t have a solid chance to chat until SF Parc (at the accelerator). We went over my life story and planned next steps. I expected him to be super anti-college; but he gave me surprising advice: go to Caltech! He mentioned some important facts that I needed to hear at the time:

• "Don't be afraid. The regret of watching someone else live the life that could've been you outweighs the comfort of safety."
• "Your life is yours; not your parents', investors', friends', or strangers'. Do what you want to do, not what you feel like you should be doing."
• "Only you have enough context to understand the best decision for yourself. Be careful and don't average advice."

I moved around a lot, so everywhere I lived felt temporary (including Caltech, for the first three months). Some places I’ve lived are:

1. Ashburn (longest)
2. Hotel Trio, Sonoma County
3. Arcadia House, North Berkeley
4. Dogpatch
5. Virginia Swan Pl, Cupertino
6. Redberry Way, San Jose
7. 29 Cecil Ave, San Jose (first time being responsible for a home)
8. 324 South Baywood Ave, San Jose
9. 524 Columbus Ave, North Beach
10. Caltech, Pasadena (2nd longest)

Each place comes with memories, and a past version of myself; the places that are burned deepest in my heart are 1, 7, 8, 3, 2 in that order.

Characters are constrained by group relations.

A character table is not filled with random character values such that the row and column orthogonality relations are satisfied. Rather, each row must come from an actual representation $\rho : G \to GL(V)$ so the matrices $\rho(g) : V \to V$ must still satisfy the same group relations.

This is easiest to see for a degree-1 representation $\rho : G \to \mathbb{C}^\times$, since $\chi_V(g) = \rho(g)$ ($\forall g \in G$). Filling in the degree-one rows in the character table is therefore the same as computing the degree-one representations for various $g \in G$.

Example 1.1 (Degree-one characters of $S_3$). Use the presentation

Let $\chi_1$ be a degree-one character. Then,

Note that possible values of $\rho_1(r)$ are $1, \omega, \omega^2$, and possible values of $\rho_1(s)$ are $\pm 1$. However, the $\zeta_3$-values for $\rho_1(r)$ do not obey $srs = r^{-1}$ and thus cannot be plausible assignments within a representation $\rho$.

Then, since $\rho$ is degree-one, $\rho(g) \in \mathbb{C}^\times$ and commutes:

so $\rho_1(r) = \rho_1(r)^2 = \rho_1(r)^3 = 1$. Similarly, $\rho_1(s) = \pm 1$. Hence, splitting across characters, we get two possible degree one character options:

so the degree-one section of $S_3$’s character table looks like this:

The takeaway: suppose someone produces a new row for $\chi_i$ of the character table and $\langle \chi_i, \chi_j \rangle = \delta_{ij}$, passing the orthogonality checks. This doesn’t mean the $\chi_i$ row is valid; rather, $\chi_i(g)$ must satisfy the group relations for each $g \in G$ (for degree-1, since $\operatorname{tr}(g) = \rho(g)$).

Note that for higher degrees, $\operatorname{tr}(g) \neq \rho(g)$, so $\chi_i(g)$ need not follow the group relations.

How orthogonality helps complete a table.

The previous section explained where character table rows come from: traces of genuine representations satisfying the group relations.

Orthogonality enters after we have some genuine characters in hand. Its role is to compare characters and determine what irreducible pieces they contain (the character rows must be of irreducible characters $\chi_1, \chi_2, \ldots, \chi_r$). (How does it check irreducible?)

We can compare characters in the character table through the inner product. Because characters are consistent over conjugacy classes,

Example 2.1 (Why do the conjugacy class sizes appear?). Suppose $G = S_3$; its conjugacy classes are

Then, let $\chi, \psi$ be class functions. From the definition,

which we do by picking representatives for the one-cycles, two-cycles, and three-cycles, as $\chi(g)\overline{\psi(g)}$ is constant over them. The conjugacy class sizes appear to count up the duplicates.

How does orthogonality check irreducibility?

Example 2.2. Recall that the two degree-one characters of $S_3$ are $\chi_1 = (1, 1, 1)$ and $\chi_2 = (1, -1, 1)$. If $\chi_1, \chi_2$ are orthogonal, i.e., if the inner product $\langle \chi_1, \chi_2 \rangle = 0$, then the two characters are irreducible. We check this:

We emphasize that inner product relation $\langle \chi_i, \chi_j \rangle = \delta_{ij}$ holds for characters only, not arbitrary class functions. The practical consequence is that we must first check if $\chi_1, \chi_2$ are characters by mapping them onto relevant representations.

What orthogonality is really saying.

For characters $\chi_1, \chi_2$ the fact that $\langle \chi_1, \chi_1 \rangle = 1$ is not merely a coincidence; this reflects that $\chi_1$ has only one irreducible component in common with $\chi_1$ (since $\chi_1$ is irreducible, that component is itself). Similarly, $\langle \chi_1, \chi_2 \rangle = 0$ reflects that $\chi_1, \chi_2$ have no irreducible components in common (and are thus orthogonal).

Example 2.3. Suppose $\chi = 2\chi_1 + \chi_2$ and $\psi = \chi_1 + 3\chi_2$ are both characters. Then, by linearity,

Note this is a shortcut to $\langle \chi, \psi \rangle = \frac{1}{|G|} \sum_{g \in G} \chi(g)\overline{\psi(g)}$ by taking advantage of $\langle \chi_i, \chi_j \rangle = \delta_{ij}$. Functionally, this is the dot product of each character’s multiplicity vectors.

• $\chi$ contains 2 copies of $\chi_1$ and one copy of $\chi_2$.
• $\psi$ contains 1 copy of $\chi_1$ and 3 copies of $\chi_2$.
• $\langle \chi, \psi \rangle$ says there are $(2)(1) = 2$ shared $\chi_1$ copies and $(1)(3) = 3$ shared $\chi_2$ copies for a total of $2 + 3 = 5$ shared irreducible character copies.

Thus, the inner product $\langle \chi, \psi \rangle$ counts the number of copies of irreducibles $\chi_1, \chi_2$ by $m_i n_i$, where each $m_i, n_i$ is a multiplicity of $\chi_1, \chi_2$ respectively.

What a character table tells us about a representation.

A character table does more than simply list irreducible characters. Once the irreducible rows are known, it lets us decompose the character of any representation into irreducible pieces.

Suppose

where $\chi_1, \ldots, \chi_r$ are irreducible characters and $m_i$ is the multiplicity of $\chi_i$. By orthogonality,

so the inner product of a character $\chi$ with one of its irreducible constituents $\chi_j$ is its multiplicity $m_j$.

Example 3.1. Consider the irreducible characters of $S_3$:

and consider the degree-4 character $\chi = (4, 0, 1)$. Then,

which correspond to the multiplicity $m_i$ of each irreducible $\chi_i$ in $\chi$. Hence, $\chi = \chi_1 + \chi_2 + \chi_3$. Checking the degrees (by plugging in the identity), we find that:

which adds up.

Note then that we immediately know $\chi$ is reducible because $\chi \neq \chi_1$ and $\langle \chi, \chi_1 \rangle = 1 \neq 0$.

The next proposition goes further into character irreducibility without finding invariant subspaces.

Proposition 3.1. Suppose $\chi : G \to \mathbb{C}$ is the character of some representation. If $\langle \chi, \chi \rangle = 1$, then $\chi$ is irreducible. If $\langle \chi, \chi \rangle > 1$, then $\chi$ is reducible.

Proof. We know $\chi = \sum_{i=1}^{r} m_i\chi_i$. Since $\langle \chi_i, \chi_j \rangle = \delta_{ij}$, $\langle \chi, \chi \rangle = \sum_{i=1}^{r} m_i^2$. The only way for this to equal 1 is if exactly one $m_i = 1$, and the remaining $m_j = 0$. Thus, $\chi = (1)\chi_i$ for some $1 \leq i \leq r$, implying $\chi$ is irreducible.

Similarly, if $\langle \chi, \chi \rangle > 1$, either $m_i = 1, m_j > 0$, or $m_i > 1$, so $\chi$ has more than a single irreducible $\chi_i$ component and is thus reducible. $\square$

Example 3.2 (The character of a direct sum). Suppose $(V, \rho_V)$ and $(W, \rho_W)$ are representations with characters $\chi_V$ and $\chi_W$ respectively. The action on the direct sum $V \oplus W$ has the representation $\rho_{V \oplus W} : G \to GL(V \oplus W)$:

with character $\chi_{V \oplus W}(g) = \operatorname{tr}(\rho_{V \oplus W}(g)) = \operatorname{tr}(\rho_V(g)) + \operatorname{tr}(\rho_W(g)) = \chi_V(g) + \chi_W(g)$.

Then, suppose $V \cong V_1 \oplus V_2 \oplus V_3$. This implies $\chi = \chi_1 + \chi_2 + \chi_3$. Conversely, if $\chi_V = 2\chi_1 + \chi_2$, this implies $V$ has decomposition $V \cong V_1 \oplus V_1 \oplus V_2$.

Character tables of direct products.

Suppose $G$ and $H$ are finite groups. A representation of $G \times H$ can be built from a representation of $G$ and a representation of $H$.

Consider $\rho : G \to GL(V)$ and $\sigma : H \to GL(W)$. On the tensor product $V \otimes W$,[1] define

Aside 4.1. An element $g \in G$ acts on $V$, and an element $h \in H$ acts on $W$. An element of $G \times H$ is a pair $(g, h)$. We want this pair to act on a vector space with both a $V$-part and a $W$-part. Call this $V \otimes W$. For now, think of its vectors as $v \otimes w$ for some $v, w \in V, W$ respectively. The definition of the $G \times H$ action is then $(g, h) \cdot (v \otimes w) = (g \cdot v) \otimes (h \cdot w)$ (since the action must be preserved). We observe that this is shorthand for $(\rho \otimes \sigma)(g, h)(v \otimes w) = \rho(g)(v) \otimes \sigma(h)(w)$.