---
# System prepended metadata

title: 'Y-Axis Podcast #2 intern notes'

---

Link to [episode](https://www.youtube.com/watch?v=Sb7jQa6u0EU&t=10s&ab_channel=TheY-AxisPodcast) 

*Applied vs pure math*

- Math taught in grade school and college class is about function and not form, like learning calculus for understanding mechanics. Pure math is more about the aesthetic. It's about proving things in an elegant way. 
    - Applied math is what Gauntlet does - agent-based simulations for different protocols to make them aware of particular risks.
    - ==Crypto has more aesthetic math hidden in the proofs than AI.==

*Q. What blew you away about pure math?*

- having an understanding of finite and infinite objects. Cantor famously proved there are multiple type of infinites. No one accepted this proof, his advisor abandoned him and he killed himself :frowning: 



> ***Cantor's diagonal argument***
> 
> To show the size of the set of all real numbers (anything that can be represented on a number line) is uncountably infinite (in other words, there are more real numbers than natural numbers {1,2,3,4,...}).
> 
> Assume that this is not true and you have this as a countable set and it contains a first element, second element, and so on, like {$𝑟_1$,$𝑟_2$,$𝑟_3$,…}.
> 
> Let's only consider all real numbers between 0 and 1.
> 
> List:
> 
> 0. $𝑟_1$ = 0. <mark style="background-color: #fdcfc6">1</mark> 4 3 5...
> 1. $𝑟_2$ = 0. 8 <mark style="background-color: #fdcfc6">1</mark> 6 9 ...
> 2. $𝑟_3$ = 0. 3 5 <mark style="background-color: #fdcfc6">5</mark> 6...
> 3. $𝑟_4$ = 0. 4 0 4 <mark style="background-color: #fdcfc6">7</mark>...
> ...
> 
> But say you construct a number that it is different from the first number at the first digit, from the second element at the second digit and so on along the diagonal. In this case we can have,
> 
> $r'$ = 0. 2 6 3 8 ...
> 
> $r'$ will be different form each $𝑟_n$ in at least one digit and hence not in our countable set. This means there exists uncountably many real numbers between 0 and 1.


- Recalls first proof of fundamental theorem of algebra (every polynomial of degree n has n roots in complex place - Gauss). You can't derive a formula for an arbitrary degree polynomial like you can do for quadratic or cubic polynomials. His graduate complex analysis class covered the most elegant proof in his complex analysis proof. =="It was one of the most elegant that I have ever seen ... seeing the same thing (proof) done elegantly was more mind blowing than the (statement) that you're seeing"==

> ***Proof***
> 
> Finding roots ($f(x) = 0$ for any applicable x) is extremely important not just for higher subfields like complex analysis or algebraic geometry but also practically used in machine learning, finance, physics, etc. This leads us to the question if every function has a root or not. It's easy to proof for odd functions ($f(-x) = -f(x)$) with real coefficients [using the intermediate value theorem](https://math.stackexchange.com/questions/689575/proof-that-every-polynomial-of-odd-degree-has-one-real-root) like $f(x) = x^3 - x$. But how about other functions like $f(x) = x^2 + 1$ which doesn't intersect $x = 0$. It turns out you can still find roots, but these roots are in the complex space $\mathbb{C}$. 
> >
> $f(x) = x^3 - x$ |  $f(x) = x^2 + 1$
> :-------------------------:|:-------------------------:
> ![](https://hackmd.io/_uploads/HkQlYjuK3.png)  |  ![](https://hackmd.io/_uploads/BJ4cYoOFn.png)
> 
> This is exactly what the Fundamental theorem of algebra (FTA) states:  ==every non-constant polynomial (eg $f(x) \neq 3$) has at least one root==.
> 
> FTA was first proposed by Gauss and he gave a proof in his dissertation in 1799 but it had a topological gaps and hence, not complete. Over the next two centuries, numerous proofs have were given from different perpectives of this theorem using topology, real or complex analysis, purely algebraic using Galois fields, etc. Read more about its history [here](https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra). The proof that Tarun mentioned came from Liouville's theorem which is a prominent result in complex analysis and is one of the more elegant and "natural" proofs.
> 
> Liouville theorem states if a function is complex-differentiable at every in the complex plane, i.e., 
> $$𝑓(𝑧)=\sum_{n=0}^\infty i = 𝑎_n \cdot z^𝑛$$ and bounded ($\exists M$ such that $|f(z)|\le M \;\forall z \in C$), then $f(z) = c$ for constant c.
> 
> 
> To prove FTA, let 
> $$p(z)=a_0+a_1\cdot z+···a_n \cdot z^n \;\;\text{with}\;\; a_n\neq 0$$ and we need to show that $p(z)=0$ for some $z \in \mathbb{C}$.
> 
> We prove this by contradiction and assume otherwise.
> Suppose, $p(z) \neq 0 \;\;\forall z \in \mathbb{C}$.
> We can construct, $f(x) = \frac{1}{z(x)}$ which is differentiable for $\forall z \in C s.t. (p \neq 0)$. 
> Now, 
> $$\begin{aligned} f(z) &= \frac{1}{|a_n\cdot z^n + a_{n-1}\cdot z^{n-1} + ... + a^0)|}
> \\ &= \frac{1}{|z^n|\cdot |a^n + \frac{a_{n-1}}{z} + ... + \frac{a^0}{z^n}|} \\
> \\ \implies \lim_{z \to \infty} f(z) &= |\frac{1}{z^n}|\cdot |\frac{1}{a^n}| = 0 \cdot |\frac{1}{a^n}| = 0 \end{aligned}$$. 
> **Outside circle:** , for $|z| \gt R, \;\; |f(z)| < 1$
> **Inside circle:** for $|z| \leq R, \;\; |f(z)| < c$ for constant c
> Let $M = max(c,e) \implies f(z) \leq M$ and using Liouville's theorem, f(z) is constant. 
> <mark style="background-color: #fdcfc6">CONTRADICTION!</mark> 
> So, there $\exists z \in C \;\;\text{s.t.}\;\; P(z) = 0$. 
> An extension to this is p(z) has n different roots (ignoring multiplicity),
>  
>  $$\begin{aligned} p_n(z)& = (z - z_0) \cdot p_{n-1}(z)
>        \\ &= (z - z_0) \cdot (z - z_1) \cdot p_{n-2}(z)
>        \\ &=\; ...
>        \\ &= (z - z_0) \cdot (z - z_1) \cdot\;\; ...  (z - z_n) \end{aligned}$$
      



How does one come up with a simpler solution or proof?

- Sometimes someone spends their entire life on a difficult problem.
- Sometimes, new subfields of math emerge and create abstractions to simplify the proof (sometimes inadvertently)
- ==Sometimes, someone in another field uses intuition they have developed completely differently. [Ed Wittens](https://en.wikipedia.org/wiki/Edward_Witten) (father of String Theory and the only non-mathematcian to win Field's medal) [reproved Morse conjecture in a simpler way](https://faculty.tcu.edu/richardson/seminars/morsetheory_igor.pdf) by mapping the problem to physical system and used the bounds of physical particles (can't reach certain state)==. Another example from cryptography: a randomness extractor is very important in cryptography (like for generating private-public key pairs) and making a less random source more random by sampling ina particular way like considering TH and HT as Heads and Tails for a 10% biased coin. Computer scientist Zeev Dvir was working on randomness extraction in mid-2000s and there was this unsolved problem called Kakeya conjecture and he accidentely proved it using essentially high school math.

> In 1917, Japanese mathematician Sōichi Kakeya posed the following question: "what is the smallest area of a plane such that you can rotate a unit needle completely, ie, $360^{\circ}$"
> 
> Intuitively, you may think a unit circle will be the an obvious answer but it's not the smallest, giving you an area of $\pi/4$. Deltoid (pictured on the left) gives you $\pi/8$. But in 1928, Besicovitch showed you move this needle within an arbitrarily small area by moving the needle in a single direction (which adds no area since needle has 0 width) and then moving it slightly to switch directions and then move back in a straight line again. 
> Deltoid       |  Besicovitch set
> :-------------------------:|:-------------------------:
> ![](https://hackmd.io/_uploads/S1zN1tdF3.gif)  |  ![](https://hackmd.io/_uploads/B1PheK_Kn.jpg)
> 
> It turned out to a very hard problem to come up with reasonable bounds for the Kakeya set $\in R^n$ especially when $n \geq 2$. In 1999, Wolfe formulated the problem for finite fields which is better formulated than the original conjecture (which is still open for dimension n > 3).
> 
> For a finite field F, a Kakeya set $K \in F^n$ iff for all vectors $v \in F^n - \{0\}$, there exists a $w \in F^n$ such that $\{w + t \cdot v | t \in F\}\;\; \text{is in K}$. People thought this was extremely difficult, even Terrance Tao couldn't prove it!!
> 
> **Conjecture (Wolff)** ==If $K \subseteq F^n$ is a Kakeya set, $|K| \geq c(n) \cdot |F|^n$ for constant function c==.
> 
> Zeev Dvir proved this in a 1 page proof in his dissertation in. 2008 using two results from polynomials in n variables as following:
> 
> **Lemma 1** Every nonzero polynomial $p(x) \in F[x1, . . . , xn]$ of degree d has at most $d \cdot q^{n−1}$ roots in $F^n$.
> 
> Proof: This can be proved by using the fact every polynomial of degree $d\geq 0$ in one variable has at most d roots. You can split $p(x) = g_0 + g_1 \cdot x_n + g_2 \cdot x_n^2+ ... + \cdot g_l \cdot x_n^l$ where $g_i \in F[x_1,x_2,..,x_{n-1}]$ and roots as (a,b) with $a \in F^{n-1}$ and use induction for the cases where $g_l(a) = 0$ and $g_l(a) \neq 0$ which gives $(d-l) \cdot q^{n-1} + l \cdot q^{n-1} = d \cdot q^{n-1}$ total roots. 
> 
> **Lemma 2** For every set $E \subseteq Fn$ of size |E| < $n+d \choose d$, there is a nonzero polynomial $p(x) \in F[x_1, . . . , x_n]$ of degree at most d that vanishes on E.
> 
> Proof: the vector space of polynomials in $F[x_1,x_2,...,x_n]$ of degree $\leq d$ has dimension as ways to choose $(x_1^{a_1} \; x_2^{a_2} ...\; x_n^{a_n})$ such that $a_1 +a_2 + ... + a_n \leq d$ and $a_i \geq 0$
> So, you have n '+'s and d '1's and hence, $n+d \choose n$ monomials.
> 
> Let's have an evaluation map $T: V_d \to F^E$ s.t. $p(x) = f(a)_{a \in E}$.
> |E| < $n+d \choose d$ $\implies dim\; F^e = |E| < dim (V_d)$
> This concludes that $f \not\equiv 0$ st $T(f) = 0$ which means p(X) vanishes on E.
> 
> **Dvir's result** Let $K \subseteq F^n$ be a Kakeya set. Then,
> $$ |K| \geq {{q+n-1} \choose n} \geq \frac{|F|^n}{n!}$$
> 
> Proof: If $|K| < {q+n-1 \choose n}$ then there exists a non-zero polynomial f such that $f(x)=0$ for all x in K and degree of $f \leq q - 1$, contrdicting Lemma 1. Hence, proved.
>
> **TLDR**: this proves the lower bound of finite field Kakeya sets. Paper [here](https://www.cs.princeton.edu/~zdvir/papers/Dvir09.pdf) and Terrance Tao's blog talking about it [here](https://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/). Proof from this [book](https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK).


- An incident where randomness was exploited was the Profanity tooling exploit with not random enough vanity addresses which famously wrecked Wintermute. [Rekted article](https://rekt.news/wintermute-rekt-2/)


Do people "create" proofs or are they transmuting it from nature?

- For applied math, you can deductively use empirical data for proving your statements. For pure math which is more inductive, you define a set of rules and properties. As an example, you can define natural numbers (N = 1,2,3,...) with an increment operator for natural numbers and the ability to count numbers below you. Every element in this set needs to follow these two rules and you can get rid of the labels like 1,2,3....
    -  During the mid twentieth century, people wanted to find impossibility results like Godel's incompleteness theorem.  ==Godel proved you there exist true statements that you can't prove true or false. This was really suprising at the time!==
    -  Most of the inconsistencies in logic are because of infinite objects. But you can't explain neural networks without infinite objects.
- "choosing properties which you care about and proving some results feels like creating something ... but if the theorem's true it was true before yout found it. It's just you found a way to describe it.... in that sense, it's not an act of God"


Are you Newton or Leibniz? Are we predetermined and moving along a set course or are we free-willed?

- =="free-will does exist but it's bounded ... you don't have it your whole life but only at particular times ... and there are lots of constraints when you have multiple creatures interacting" and these constraints are very detailed"==

Is it taboo in the math community to be spiritual?

- mathematicians are more into (weird kind of) spirituality than other scientists and like really rigid and militant rules. Some are strict Catholics or orthodox or Jewish or Hindus. Ramanujan killed himself because he thought a demon spirit was haunting him. Ted Kaczynski or the unabomber was also a math professor.

Is theoretical mathematics a hard field like physics where the obvious problems are already solved? What is the pathway for someone to get into it?

- =="You don't need money to do math .. you really need a notebook and a pencil and that's it". This is the difference to other fields.==
- Interestingly, theoretical physics is more "snobbish" and full of nonsensical "made-up" papers. Example - [famous Bogdanov twins' paper](https://en.wikipedia.org/wiki/Bogdanov_affair)
- "(what) I've always found most interesting is when you can translationally do math .. you're trying to solve some problems in some other fields and then you accidentally find some different representationof an existing problem in math"

Foundational math in crypto vs AI

- It is effectively necessary to having strong foundational math. ==In cryptography you're assuming an adversarial model where an adversary needs to expend exponentially more computational resources than an honest party. You need to be precise about who the adversary is, what functionality they have, what compute they are using?==
- In AI, it's "I have a model and some data. I don't exactly know if the model would or wouldn't predict." You're averaging over many instances. In AI, you care about the average case behavior and in cryptography and finance, you need to model worst case behavior, because you'll make completely differently predictions otherwise. In crypto, it's more like "you'll die if you mispredict" vs in AI, it's "try not to mispredict but only as an after-effect"
- It's harder to write software in the blockchain space and you need a concrete model and formal math and less "I threw a bunch of things and it works"
- Tarun's first boss Jon Jumper, was head of Deepmind Science Division and won Brekthrough Prize for AlphaFold [last year](https://twitter.com/brkthroughprize/status/1572934739740086273?lang=en).

Transformers

- A neural network is essentially a function which takes in an input vector and outputs another vector trying to approximate a particular model which is matrix multiplcation and component-wise non-linearilities.
- Traditional neural networks which are fee-forward and cannot do sequencely dependence things like coming up with the next word in a sentence.
- Recurrent neural network, allowed to jump backwards. "quick fox jump _" fox comes back into the context which predicting the next word.
- Transformers uses a hack, replicates RNN. Reinject the entire input into each side so you don't forget. Notion of attention, "fox" keeps showing up and will stay in context more or attenuated. 

Why was crypto the perfect medium for zk cryptography?

- The marketing term zk encapsulating actual MPC (multi-party computation), FHE (fully-homomorphic encryption), ZK or more commonly succinct proofs.
- Back in the 1990s, Arthur Merlin proofs were created where you (prover) taught or proved to someone (verifier) without revealing the actual witness interactively. But, this was impractical because of the many rounds of communication needed. Then came the Fiat-Shamir transform which allows you to make these proofs non-interactive.
- These came from the IP complexity theory, which is a hierarchy of problems in computer science and any two problems in the same complexity class can be reduced to each other. This translates to someone capable of solving a harder computational class problem and proving to you they have the answer without you needing the same amount of compute.
- One of the seminal results in theoritical Computer Science is set of interactive proofs is the set of computation which requires polynomial input.
- This was divorced from real world applications and you weren't able to do this for generic computations. But in 2012, Gentry proved that you can take any piece any program and convert it to this particular sort of like matrix style of operations and you can prove your code works by randomly sampling and proving some particular property of these matrices. This was the introduction of Rank One Constrained Systems.
- ==Blockchain are exactly the same from the complexity theory standpoint. You can use a light client to verify the network did same computation correctly without rerunning it. You can use ZK for this.== But where do you what such compute?
    - zk rollups - state transitions 
    - bridging - balance of the other chain is correct without having to parse the VM
    - want some off-chain computation which can be verifible like a oracle.
- resource restriction gives you the incentive.
- The scale at which we can do zk is not sufficient for private-ML.

Where do you see ZK tech going forward in the space?

- mobile wallet experience. 
- cross-chain compasibility. instead of having one VM trying to emulate another VM completely, all you need a is a agreed upon proof system and each side has they own code for verifying it.
- there's a whole class of mechanism where you can zk to execute the mechanisms you can provide explicit price guarantees or like auditability manipulation guarantees and you can show that without the ZK part you have strictly worse pricing. [Paper on zk mechanism design](https://arxiv.org/abs/2302.05590).
    - Case in point. Credible auctions where you can have the three critical properties of an "awesome" auction - buyers bid what they actual value the item, seller not placing fake bids or manipulating prices or censoring comunication between bidders, and you need bounded computation complexity. You can turn it into one round of communication with SNARKs which is important for blockchains. Assuming zk commitments you can show bounds on the "safe deviation" of the sellers. This gives tangible economic gurantees.
    - DOJ is suing Google over placing fake bids. Buyers cannot tell without talking to each other. 


Any life advice or habits which have improved your life?

- =="You only have one reputation and try to do things which doesn't do damage to it. A lot of people are willing to trade reputation for short-term gains at different points and that inevitably does bite them ... once you start with this as an axiom, you can induct a bunch of other things that you shouldn't do."==





