Feed Aggregator
Generated with static-feed-aggregator
Our Obsession with Proofs
Computational Complexity — 5/1/2024
Bullinger’s post on this blog last week focused on Vijay Vazirani’s public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why does Vijay, and theoretical computer science in general, obsess over proofs? You can’t…
Machines and tools
Crooked Timber — 5/1/2024
It’s International Workers Day, still celebrated as the May Day public holiday here in Queensland, at least when the Labor party is in office. So, it’s a good day for me to set out some tentative thoughts on work and its future. Via Matt McManus, I…
The destruction of Argentina’s higher education and science system
Crooked Timber — 4/30/2024
Scientific research, academic knowledge production, and higher education are under an obscene and direct attack today in Argentina. Milei’s attack is not an isolated case. To a certain extent, it is part of a global phenomenon, i.e. the rampant…
Line Bundles on Complex Tori (Part 5)
The n-Category Café — 4/30/2024
We prove the main conjecture from last time: a description of the hexagonal tiling lattice using Eisenstein integers.
Line Bundles on Complex Tori (Part 4)
The n-Category Café — 4/30/2024
Today I’ll head toward an explicit bijection between principal polarizations of the Eisenstein surface and centers of hexagons in the hexagonal tiling honeycomb. I won’t quite get there, but I’ll lay the groundwork.
[Part 2] The YouTube script: youtube2llm.py
Proses.ID — 4/30/2024
Hey, as promised, I’ll start introducing the different scripts in the Nootroscripts project. youtube2llm.py [TOC] Overview: analyse, embed, and ask anything about the content of…
I don’t want to be a deadweight
Proses.ID — 4/29/2024
was triggered yesterday morning I find it hard to even replay and describe what happened even though it’s as simple as: mom asked me if…
Math Thoughts Inspired by the TV show Succession
Computational Complexity — 4/29/2024
I watched Succession one-episode-a-day on treadmill for 39 days. I’m glad I did this in 2023 since Season 2 aired its last show on Oct 19, 2019, and Season 3 had its first show on Oct 17, 2021, so I would have been in suspense (or at least as much…
Line Bundles on Complex Tori (Part 3)
The n-Category Café — 4/28/2024
Today I’ll compute the Néron–Severi group of a very symmetrical abelian surface built from the Eisenstein integers. Then I’ll begin to explain a nice picture of a ‘slice’ of this group.
Sunday photoblogging: Pézenas
Crooked Timber — 4/28/2024
Going Meta on Culture Wars
Crooked Timber — 4/26/2024
Culture wars have two main functions. First, to split an existing, dominant social or political coalition apart by the clever use of wedge-issues. (Not all wedge-issues are a part of a culture war.) So, a culture war reveals a latent or induces…
Is Persistence an Anachronism?
Computational Complexity — 4/24/2024
Guest post by Martin BullingerVery recently, Vijay Vazirani’s paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted to Mathematics of Operations Research. For the first time, it gives a complete and…
Counting Points on Elliptic Curves (Part 3)
The n-Category Café — 4/24/2024
Starting from a simple definition of the L-function of an elliptic curve, we can recover the complicated-looking definition one often sees.
Moving On From Kent
The n-Category Café — 4/23/2024
Kent Philosophy comes to an end
Intelligent Comments on Bill’s G.H. Hardy/Avi W post that we did not post.
Computational Complexity — 4/21/2024
I posted (see here) about Avi Wigderson being a counterexample to two of G.H. Hardy’s opinions:1) Hardy thought Math was a young man’s game. I got some good comments on this. Some agreed and some disagreed. 2) Hardy thought applied math is dull. I…
Sunday photoblogging: crossroads
Crooked Timber — 4/21/2024
The Modularity Theorem as a Bijection of Sets
The n-Category Café — 4/20/2024
Bruce Bartlett floats a version of the Modularity Theorem for elliptic curves that frames it as an explicit bijection between sets, and has a question for the experts.
Online talks
Crooked Timber — 4/20/2024
I’ve been doing a bunch of talks and events online, mostly not CT related, but a couple that might be interesting to readers. One that certainly is is this conversation with Francis Spufford, which is a coda to Red Plenty. Some of my bits of the…
Expertise and naval power
Crooked Timber — 4/20/2024
Robert Farley has replied to my recent post on the obsolescence of naval power. Unlike our previous exchange, a pile-on where I was (as he points out) in a minority of one, Robert’s tone is mostly civil this time, and I intend to reciprocate. Our…
Favorite Theorems: Quantum Provers
Computational Complexity — 4/19/2024
For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier, then two entangled provers can convince a polynomial-time verifier.MIP* =…
The Quintic, the Icosahedron, and Elliptic Curves
The n-Category Café — 4/18/2024
Bruce Bartlett has a new expository article on “The quintic, the icosahedron, and ellliptic curves”.
Wenar on why you shouldn’t try to help poor people
Crooked Timber — 4/18/2024
In all the discussion of Leif Wenar’s critique of Effective Altruism , I haven’t seen much mention of the central premise: that development aid is generally counterproductive (unless, perhaps, it’s delivered by wealthy surfers in their spare time)….
Pythagorean Triples and the Projective Line
The n-Category Café — 4/17/2024
How pondering Pythagorean triples leads us into the algebraic geometry of conics.
Academic Freedom, State Legislatures and Public Universities (Wisconsin edition).
Crooked Timber — 4/17/2024
Gina’s post on Indiana’s DEI-related law came at a fortuitous time for me, because last week I participated in a panel about State Legislatures, Academic Freedom and Public Universities. The panelists were given about 6 minutes to present some…
Crooked Timberish books and other writings
Crooked Timber — 4/17/2024
I’m sure Crooked Timber readers would been keen to learn of exciting new books out just now from Daniel Davies and Kieran Healy. Marion Fourcade and Kieran Healy have published The Ordinal Society , arguing that “argue that technologies of…
Avi Wigderson is a counterexample to TWO stupid thoughts of G.H. Hardy
Computational Complexity — 4/15/2024
Recently1) Avi Wigderson won the Turing Award (See blog posts by Fortnow-here, Scott-here, Lipton-Regan here, and the ACM announcement here). The last time I could find when Fortnow-Gasarch, Scott, Lipton-Regan all blogged on the same topic was…
Semi-Simplicial Types, Part II: The Main Results
The n-Category Café — 4/15/2024
Part 2 of a 3-part series about displayed type theory and semi-simplicial types.
Semi-Simplicial Types, Part I: Motivation and History
The n-Category Café — 4/15/2024
Part 1 of a 3-part series about displayed type theory and semi-simplicial types.
Sunday photoblogging: Canal Saint-Martin, Paris (3)
Crooked Timber — 4/14/2024
Limitarianism update
Crooked Timber — 4/13/2024
Since my book Limitarianism: The Case Against Extreme Wealth came out, first in Dutch at the end of November, and then in the US and in the UK a few weeks later, I’ve given more than 60 media interviews and talks. Among them was a long interview in…
The making of Icehenge
Crooked Timber — 4/12/2024
Last year, I received an email asking if I would write an introductory essay for the Tor Essentials reissue of Kim Stanley Robinson’s novel Icehenge. It took me approximately thirty seconds to convince myself that this was not some kind of…
Machine Learning Jobs for Category Theorists
The n-Category Café — 4/11/2024
Symbolica is hiring category theorists. It’s already hired some, and there are job ads for 6 more. They are hiring in the UK and Australia.
Avi wins the Turing Award
Computational Complexity — 4/10/2024
The ACM announced that Avi Wigderson, a force in computational complexity and beyond, will receive the 2023 A. M. Turing Award (Quanta article). This is the first primarily complexity theorist to win the award since Andy Yao in 2000. Avi can add…
Rance Cleaveland passed away on March 27, 2024. He will be missed
Computational Complexity — 4/9/2024
My friend and colleague Rance Cleaveland passed away on March 27, 2024 at the age of 62. He was a professor at The University of Maryland at College Park in the Computer Science Department. He worked in Software Engineering. He did program…
East German history
Crooked Timber — 4/9/2024
I’ve posted a few times over the years about a trip I made with my partner to Leipzig in East Germany back in 1984, and I confess that the now-defunct country retains a kind of fascination for me. My rather banal judgement then and now is that the…
Two ideas for using LLMs in software development
Proses.ID — 4/8/2024
Two ideas for using LLMs in software development Other than coding assistants and code completions, Software developers spend substantial amount of time making technical decisions…
Nootroscripts: A suite of LLM-powered scripts for curious curators to help synthesize content in different formats and sources, more efficiently
Proses.ID — 4/8/2024
Hey friends, today I am releasing my LLM-related Python scripts for working with youtube, podcasts, and articles. These CLI-based scripts have boosted my consumption and…
Sunday photoblogging: Canal Saint-Martin, Paris (2)
Crooked Timber — 4/7/2024
Answer to Question. MetaQuestion remains unsolved
Computational Complexity — 4/3/2024
In a prior post I asked the following question:find x,y,z positive natural numbers such that the following is true:\(\frac{x}{y+z} + \frac{y}{x+z} + \frac{z}{x+y} = 4.\)I first saw the question in a more fun way:I did not put the answer in the…
A Math Question and a Meta Question
Computational Complexity — 4/2/2024
1) Question: find x,y,z natural numbers such that the following is true:\(\frac{x}{y+z} + \frac{y}{x+z} + \frac{z}{x+y} = 4.\)I was first presented the problem a more fun way:(NOTE- a commenter pointed out that ``Natural Numbers’’ and `Positive…
Unusual Tips for Parenting Toddlers
Math ∩ Programming — 4/1/2024
It’s April Cools! Last year I wrote about friendship bracelets and the year before about cocktails. This year it’s parenting. Parenting articles are a dime a dozen and always bury the lede behind a long story. I’ll skip that. How to think about…
Can you feel the machine?
Computational Complexity — 3/29/2024
In the recent academy award winning movie Oppenheimer, Niels Bohr tests a young Oppenheimer.Bohr: Algebra’s like sheet music, the important thing isn’t can you read music, it’s can you hear it. Can you hear the music, Robert?Oppenheimer: Yes, I…
Why Mathematics is Boring
The n-Category Café — 3/29/2024
Some thoughts on how to make mathematics interesting.
The Softening of Computing Jobs: Blip or Trend?
Computational Complexity — 3/27/2024
Tech companies are performing exceptionally well, driving the S&P 500 to new heights with their soaring stock prices. However, the tech sector, apart from AI, expects a job decline to persist throughout the year, accompanied by a tougher hiring…
I know what A-B-C-D-F mean but what about V? X? HP?
Computational Complexity — 3/25/2024
I am looking at LOTS of transcript of students who applied for my program REU-CAAR so I sometimes come across grades that I don’t understand. The transcript does not have a guide to them, and I have been unable to find the meaning on line.Normal…
Counting Points on Elliptic Curves (Part 1)
The n-Category Café — 3/22/2024
One commonly seen definition of the L-function of an elliptic curve looks really ugly. Let’s dig into it a bit - maybe we can improve it.
Grad Student Visit Day: That was then, this is now.
Computational Complexity — 3/17/2024
(Harry Lewis helped me with this post.) March 15 was UMCP Computer Science Grad Student Visit Day. I suspect many of my readers are at schools that had their Grad Student Visit Day recently, or will have it soon. In 1980 I got into Harvard Grad…
Counting Points on Elliptic Curves (Part 2)
The n-Category Café — 3/14/2024
Four things can happen when you take an elliptic curve with integer coefficients and look at it over a finite field. There’s good reduction, bad reduction, ugly reduction and weird reduction. Let’s see examples of these four cases, and how they…
Translation in Context
Computational Complexity — 3/13/2024
La Scala in MilanGoogle translate generally impresses but consider this translation from a short Italian news article. I boldfaced a few items.Not scheduled at the premiere of Mozart’s Die Entführung aus dem Serail (The Abduction from the Seraglio)…
The Thrill of Seeing Your Name in Print is Gone
Computational Complexity — 3/11/2024
In the 1980’s and 1990’s when I got a paper accepted to a journal or conference it seemed important to see it in print. Having a paper accepted was nice, but it didn’t seem real until I held the conference proceedings or journal in my hand. I…
Communism Is Better
Abuse of Notation — 3/10/2024
title: Which is better layout: microblog category: microblog tags: capitalism joke — Too much of the left wing/right wing discussion is about which is better, when every ideology is bad when pushed to the extreme: If you lean to the far right you…
Conformity is not the way
Abuse of Notation — 3/10/2024
What is conformism. Dictionary defines it as “willingness to conform”, but I think a better definition of conformism would be the want, desire to conform (as everyone are willing to conform when given the right motivation). This is not a complete…
On Hokusai
Abuse of Notation — 3/10/2024
I consider Hokusai the greatest artist of all time, because he contributed to the two most prominent genres in visual art - landscapes and porn.
Nothing To Prove
Abuse of Notation — 3/10/2024
title: Nothing to prove layout: microblog category: microblog tags: joke math — “I think I will stop doing logic, I feel like I have nothing to prove.”
Tabletop Games Based on Math Problems
Math ∩ Programming — 3/9/2024
There’s a family of tabletop games that are based directly on a nontrivial mathematics problem. As a casual and fun way to inaugurate my new blog (migrated from Wordpress to Hugo, after my work on getting better LaTeX mathmode support in Hugo), I…
Favorite Theorems: Sensitivity
Computational Complexity — 3/7/2024
Our next favorite theorem gave a relatively simple proof of the sensitivity conjecture, a long-standing problem of Boolean functions.Induced subgraphs of hypercubes and a proof of the Sensitivity Conjectureby Hao HuangConsider the following…
Modular Curves and Monstrous Moonshine
The n-Category Café — 3/4/2024
Playing around with Monstrous Moonshine and modular curves.
The letter to recommend John Nash was ``The Best Recomendation Letter Ever’’- I do not think so.
Computational Complexity — 3/3/2024
There is an article about the letter Richard Duffin wrote for John Nash that helped John Nash get into Princeton: here. The title of the article is The Best Recommendation Letter Ever.The article appeared in 2015. The letter is dated Feb 11,…
Gödel incompleteness, graduate course, Notre Dame, Fall 2024
Joel David Hamkins — 3/2/2024
This will be a graduate course at the University of Notre Dame. Course title: Gödel incompleteness Course description. We shall explore at length all aspects of the Gödel incompleteness phenomenon, covering Turing’s solution of the…
Failing definite descriptions, Notre Dame Food for Thought Seminar, March 2024
Joel David Hamkins — 3/2/2024
I gave a talk for the Food for Thought seminar for the Notre Dame philosophy department. The topic concerned definite descriptions, particularly the semantics that might be given when one extends first-order logic to include the iota operator, by…
A Quantum State
Computational Complexity — 2/28/2024
Illinois’ most famous citizen working on a quantum computerThe governor of Illinois, JB Pritzker, unveiled his budget last week including $500 million for quantum computing research. Is this the best way to spend my tax dollars?As long-time readers…
When is it worth the time and effort to verify a proof FORMALLY?
Computational Complexity — 2/25/2024
(This post was inspired by Lance’s tweet and later post on part of IP=PSPACE being formally verified.) We now have the means to verify that a proof (prob just some proofs) is correct (one could quibble about verifying the verifier but we will not…
Sumchecks and Snarks
Computational Complexity — 2/21/2024
Last summer as I lamented that my research didn’t have real world implications, one of the comments mentioned the sumcheck protocol used for zero-knowledge SNARKs. I tried to figure out the connection back then but got lost in technical…
ChatGPT thinks Graph Isomorphism has real applications. Is it right?
Computational Complexity — 2/19/2024
Lance did a post on Babai’s result on Graph Isomorphism (see here). I then did a post asking if Graph Isomorphism has real applications (see here). Lance proofread my post (There were some typos! Really!) and then he was inspired to ask ChatGPT…
Change
Computational Complexity — 2/15/2024
An academic field often organizes itself pulling ideas from its own field. For example, students on the economics faculty job search can signal at most two schools, without giving any other rules on how the signals should be used, allowing…
How the continuum hypothesis could have been a fundamental axiom, UC Irvine Logic & Philosoph of Science Colloquium, March 2024
Joel David Hamkins — 2/12/2024
This will be a talk for the Logic and Philosophy of Science Colloquium at the University of California at Irvine, 15 March 2024. Abstract. With a simple historical thought experiment, I should like to describe how we might easily have … Continue…
Are there any REAL applications of Graph Isomorphism?
Computational Complexity — 2/11/2024
Lance’s post on Babai’s result on Graph Isomorphism (henceforth GI) inspired some random thoughts on GI. (Lance’s post is here.) 1) Here is a conversation with someone who I will call DAVE. This conversation took place in the late 1980’s. BILL: You…
What if your potentialism is implicitly actualist? Oxford conference, March 2024
Joel David Hamkins — 2/10/2024
This will be a talk at the conference Challenging the Infinite, March 11-12 at Oxford University. (Please register now to book a place.) Abstract Many commonly considered forms of potentialism, I argue, are implicitly actualist in the sense that a…
Favorite Theorems: Graph Isomorphism
Computational Complexity — 2/7/2024
We start our favorite theorems of the last decade with a blockbuster improvement in a long-standing problem. Graph Isomorphism in Quasipolynomial Time by László BabaiThe graph isomorphism problem takes two graphs G and H both on n nodes and asks if…
Space-filling curves, constructively
Mathematics and Computation — 1/30/2024
In 1890 Giuseppe Peano discovered a square-filling curve, and a year later David Hilbert published his variation. In those days people did not waste readers’ attention with dribble – Peano explained it all on 3 pages, and Hilbert on just 2 pages,…
The covering reflection principle, Notre Dame Logic Seminar, February 2024
Joel David Hamkins — 1/29/2024
This will be a talk for the Notre Dame Logic Seminar on 6 February 2024, 2:00 pm. Abstract. The principle of covering reflection holds of a cardinal $\kappa$ if for every structure $B$ in a countable first-order language there is … Continue reading →
The things you fear
Abuse of Notation — 1/21/2024
The things you fear will happen are already happening (else there would be no way to fear them). The only way to stop them from happening is to stop fearing them
Haskell
Abuse of Notation — 1/21/2024
“Oh, in Haskell this app is just a one-liner!” The one-liner: app a b c d e= runMonadT ( (LiftValue a b c) ! stop) . \a -> d(a) $ e
Bash
Abuse of Notation — 1/20/2024
I think that bash is so popular because it is so terrible language and hard to work with, that every time you make something work you feel like a wizard and your dopamine is to the roof
Battling my ego
Abuse of Notation — 1/20/2024
Battling my ego. The stage is set. I turn to it and say “It’s gonna hurt ME a lot more than it hurts YOU”.
Plato’s Republic and anarchy
Abuse of Notation — 1/20/2024
The more I reread The Republic, the more I think that the guy who argued with Socrates at the beginning had a solid point — justice is whatever the rulers say. Incidentally, this argument leads straight to anarchy (the system which is taken to be…
The concept of maturity as a means of societal control
Abuse of Notation — 1/16/2024
If you’re not a socialist before you’re twenty-five, you have no heart; if you are a socialist after twenty-five, you have no head. – anonymous I am young enough that there are still people telling me that they too were…
The Gödel incompleteness phenomenon, interview with Rahul Sam
Joel David Hamkins — 1/14/2024
Please enjoy my conversation with Rahul Sam for his podcast, a sweeping discussion of topics in the philosophy of mathematics—potentialism, pluralism, Gödel incompleteness, philosophy of set theory, large cardinals, and much more.
Half Haunted: The 1/2 in Harish-Chandra via the Fourier Transform
Good Fibrations — 12/31/2023
This post is written together with Josh Mundinger. Last time, we compared the Harish-Chandra isomorphism (Z(U\mathfrak g) \cong (\text{Sym} \mathfrak h)^{W,\cdot}) for (\mathfrak g= \mathfrak{sl}_2) to the Duflo isomorphism (Z(U\mathfrak g)…
Pluralism in the foundations of mathematics, ASL invited address, joint APA/ASL meeting, New York, January 2024
Joel David Hamkins — 12/18/2023
This will be an invited ASL address at the joint meeting of the ASL with the APA Eastern Division conference, held in New York 15-18 January 2024. My talk will be 16 January 2024 11:00 am. Abstract. I shall give … Continue reading →
The computable model theory of forcing, Rutgers Logic Seminar, December 2023
Joel David Hamkins — 11/23/2023
This will be a talk for the Rutgers University Logic Seminar, December 4, 2023. Abstract. I shall discuss the computable model theory of forcing. To what extent can we view forcing as a computational process on the models of set … Continue reading →
MLIR — A Global Optimization and Dataflow Analysis
Math ∩ Programming — 11/15/2023
Table of Contents In this article we’ll implement a global optimization pass, and show how to use the dataflow analysis framework to verify the results of our optimization. The code for this article is in this pull request, and as usual the commits…
Test fediverse via activitypub
Proses.ID — 11/8/2023
test to mastodon?
The Wordle and Absurdle numbers, CUNY Logic Workshop, November 2023
Joel David Hamkins — 11/7/2023
This will be a talk for the CUNY Logic Workshop, 17 November 2023. Abstract. We consider the game of infinite Wordle as played on Baire space $\omega^\omega$. The codebreaker can win in finitely many moves against any countable dictionary…
What is second-order predicate modal logic? FoMoLo Seminar, February 2024
Joel David Hamkins — 11/3/2023
This will be a talk for the First-order Modal Logic (FoMoLo) Seminar, 12 February 2024. The talk will take place online via Zoom—contact the organizers for access. Abstract. What is or should be the potentialist account of classes? There are ……
MLIR — Lowering through LLVM
Math ∩ Programming — 11/1/2023
Table of Contents In the last article we lowered our custom poly dialect to standard MLIR dialects. In this article we’ll continue lowering it to LLVM IR, exporting it out of MLIR to LLVM, and then compiling to x86 machine code. The code for this…
Nsncd, Anniversary Updates
AlternativeBit — 10/30/2023
Last year, flokli and I worked towards re-using TwoSigma’s Nsncd as the main NixOS Nscd daemon. What is that even about? Well, Nscd is a Glibc daemon that was originally meant to cache the host/user resolution requests. It’s mostly obsolete by now,…
MLIR — Dialect Conversion
Math ∩ Programming — 10/23/2023
Table of Contents In previous articles we defined a dialect, and wrote various passes to optimize and canonicalize a program using that dialect. However, one of the main tenets of MLIR is “incremental lowering,” the idea that there are lots of…
The limit of (your) language
Proses.ID — 10/18/2023
“The limits of my language means the limits of my world.” — Ludwig Wittgenstein I’ve always taken this to mean I need to extend and…
Socks, a matching game based on an additive combinatorics problem
Math ∩ Programming — 10/14/2023
Can you find a set of cards among these six, such that the socks on the chosen cards can be grouped into matching pairs? (Duplicate pairs of the same sock are OK) Spoilers: If the cards are indexed as 1 2 3 4 5 6 Then the following three subsets…
The surprising strength of second-order reflection in urelement set theory, Luminy, October 2023
Joel David Hamkins — 10/11/2023
This will be a talk at the XVII International Luminy Workshop in Set Theory at the Centre International de Rencontres Mathématiques (CIRM) near Marseille, France, held 9-13 October 2023. Abstract. I shall give a general introduction to urelement…
What is potentialist second-order logic? Konstanz Actualism and Potentialism Conference 2023
Joel David Hamkins — 9/20/2023
This is a talk for the Actualism and Potentialism Conference at the University of Konstanz, 28-29 September 2023. Also on Zoom: 928 0804 3434. Abstract. What is or should be the potentialist account of classes? It turns out that there … Continue…
MLIR — Canonicalizers and Declarative Rewrite Patterns
Math ∩ Programming — 9/20/2023
Table of Contents In a previous article we defined folding functions, and used them to enable some canonicalization and the sccp constant propagation pass for the poly dialect. This time we’ll see how to add more general canonicalization…
Encoding Schemes in FHE
Math ∩ Programming — 9/18/2023
In cryptography, we need a distinction between a cleartext and a plaintext. A cleartext is a message in its natural form. A plaintext is a cleartext that is represented in a specific way to prepare it for encryption in a specific scheme. The…
Infinite-Games Workshop
Joel David Hamkins — 9/17/2023
Welcome to the Infinite-Games Workshop, beginning Autumn 2023. The past ten years has seen an explosion in the study of infinite games, for researchers are now investigating diverse infinite games, including infinite chess, infinite draughts,…
Half Haunted: Relating the 1/2’s in Duflo and Harish-Chandra
Good Fibrations — 9/16/2023
This post is written together with Josh Mundinger. We seek to understand the relations between (1/2)’s that appear across mathematics. From the Riemann Hypothesis to the L2 norm, we aim to see the myriad and enticing ways this unfurls; each…
MLIR — Verifiers
Math ∩ Programming — 9/13/2023
Table of Contents Last time we defined folders and used them to enable some canonicalization and the sccp constant propagation pass for the poly dialect. This time we’ll add some additional safety checks to the dialect in the form of verifiers. The…
MLIR — Folders and Constant Propagation
Math ∩ Programming — 9/11/2023
Table of Contents Last time we saw how to use pre-defined MLIR traits to enable upstream MLIR passes like loop-invariant-code-motion to apply to poly programs. We left out -sccp (sparse conditional constant propagation), and so this time we’ll add…
MLIR — Using Traits
Math ∩ Programming — 9/7/2023
Table of Contents Last time we defined a new dialect poly for polynomial arithmetic. This time we’ll spruce up the dialect by adding some pre-defined MLIR traits, and see how the application of traits enables some general purpose passes to optimize…
Computing Percentages Easier
Math ∩ Programming — 9/6/2023
Problem: Compute 16% of 25 in your head. Solution: 16% of 25 is equivalent to 25% of 16, which is clearly 4. This is true for all numbers: $x\%$ of $y$ is always equal to $y\%$ of $x$. The first one is $\frac{x}{100} y$ and the second is…
MLIR — Defining a New Dialect
Math ∩ Programming — 8/21/2023
Table of Contents In the last article in the series, we migrated the passes we had written to use the tablegen code generation framework. That was a preface to using tablegen to define dialects. In this article we’ll define a dialect that…
Philosophy of Mathematics and Truth, interview with Matthew Geleta on Paradigm Podcast
Joel David Hamkins — 8/18/2023
We had a sweeping discussion touching upon many issues in the philosophy of mathematics, including the nature of mathematical truth, mathematical abstraction, the nature of mathematical existence, the meaning and role of proof in mathematics, the…
An exploration of infinite games—infinite Wordle and the Mastermind numbers, Harvard, October 2023
Joel David Hamkins — 8/15/2023
This will be a talk 16 October 2023 (Note new date!) for the Colloquium of the Harvard Center for Mathematical Sciences and Applications (CMSA). Abstract: Let us explore the nature of strategic reasoning in infinite games, focusing on the cases of…
On indefinite truth values
Mathematics and Computation — 8/13/2023
In a discussion following a MathOverflow answer by Joel Hamkins, Timothy Chow and I got into a chat about what it means for a statement to “not have a definite truth value”. I need a break from writing the paper on countable reals (coming soon in a…
MLIR — Using Tablegen for Passes
Math ∩ Programming — 8/10/2023
Table of Contents In the last article in this series, we defined some custom lowering passes that modified an MLIR program. Notably, we accomplished that by implementing the required interfaces of the MLIR API directly. This is not the way that…
MLIR — Writing Our First Pass
Math ∩ Programming — 8/10/2023
Table of Contents This series is an introduction to MLIR and an onboarding tutorial for the HEIR project. Last time we saw how to run and test a basic lowering. This time we will write some simple passes to illustrate the various parts of the MLIR…
MLIR — Running and Testing a Lowering
Math ∩ Programming — 8/10/2023
Table of Contents Last time, we covered a Bazel build system setup for an MLIR project. This time we’ll give an overview of a simple lowering and show how end-to-end tests work in MLIR. All of the code for this article is contained in this pull…
MLIR — Getting Started
Math ∩ Programming — 8/10/2023
Table of Contents As we announced recently, my team at Google has started a new effort to build production-worthy engineering tools for Fully Homomorphic Encryption (FHE). One focal point of this, and one which I’ll be focusing on as long as Google…
Google’s Recent FHE work, and starting HEIR
Math ∩ Programming — 8/10/2023
Today my team at Google published an article on Google’s Developers Blog with some updates on what we’ve been doing with fully homomorphic encryption (FHE). There’s fun stuff in there, including work on video processing FHE, compiling ML models to…
Variations on Weihrauch degrees (CiE 2023)
Mathematics and Computation — 7/28/2023
I gave a talk “Variations on Weihrauch degrees” at Computability in Europe 2023, which took place in Tbilisi, Georgia. The talk was a remote one, unfortunately. I spoke about generalizations of Weihrauch degrees, a largely unexplored territory that…
Continuity principles and the KLST theorem
Mathematics and Computation — 7/19/2023
On the occasion of Dieter Spreen’s 75th birthday there will be a Festschrift in the Journal of Logic and Analysis. I have submitted a paper “Spreen spaces and the synthetic Kreisel-Lacombe-Shoenfield-Tseitin theorem”, available as a preprint…
Short form content is not making us stupid and more distracted
Proses.ID — 7/14/2023
I think short form content has been unfairly demonised and long form overly romanticised Short form is NOT making us stupid and distracted. shorter content…
Short form vs long form
Proses.ID — 7/14/2023
Again about the previous post: I think short form content has been unfairly demonised and long form overly romanticised A better way to think about…
text is a temporary lossy workaround
Proses.ID — 7/14/2023
as an extremely text-biased person with an unjustifiable fetish of long-form text, it pains me to have to start to accept that text (hence writing…
our phones didn’t destroy our attention span
Proses.ID — 7/14/2023
perhaps this “social media and smartphones have ruined our attention span” issue is really just FOMO on steroid and less an actual neurological change? do…
Two’s Complement and Group Theory
Math ∩ Programming — 7/10/2023
Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the second was the two’s complement representation of a negative…
Isomorphism invariance and isomorphism reflection in type theory (TYPES 2023)
Mathematics and Computation — 6/15/2023
At TYPES 2023 I had the honor of giving an invited talk “On Isomorphism Invariance and Isomorphism Reflection in Type Theory” in which I discussed isomorphism reflection, which states that isomorphic types are judgementally equal. This strange…
The Nix, OpenGL and Ubuntu Integration Nightmare
AlternativeBit — 4/20/2023
In this article, we’re about to dive into the uncharted OpenGL on Linux waters. After briefly explaining how the OpenGL calls are routed from your application to the GPU, we’ll look at the NixOS special case. We’ll then explore how we can run the…
We’re Knot Friends
Math ∩ Programming — 4/1/2023
It’s April Cools again. For a few summers in high school and undergrad, I was a day camp counselor. I’ve written before about how it helped me develop storytelling skills, but recently I thought of it again because, while I was cleaning out a…
New Video Podcast: fAQ
Math3ma — 3/28/2023
In a bit of fun news, I’ve just launched a new video podcast with my coworker Adam Green. This new video series, which we’re calling fAQ, consists of casual conversations between me and Adam on basic ideas in quantum physics and eventually some…
What is Superposition, Really?
Math3ma — 3/28/2023
The next episode in the fAQ video podcast is now up! As mentioned last time, this is a new project I’ve embarked on with Adam Green where we chat about different ideas in quantum physics and (at some point) AI. Our primary goal is simply to help…
Modeling Sequences with Quantum States
Math3ma — 3/16/2023
In the past few months, I’ve shared a few mathematical ideas that I think are pretty neat: drawing matrices as bipartite graphs, picturing linear maps as tensor network diagrams, and understanding the linear algebraic (or “quantum”) versions of…
Understanding Entanglement With SVD
Math3ma — 3/16/2023
Quantum entanglement is, as you know, a phrase that’s jam-packed with meaning in physics. But what you might not know is that the linear algebra behind it is quite simple. If you’re familiar with singular value decomposition (SVD), then you’re 99%…
What is Quantum Technology?
Math3ma — 3/16/2023
Today I’m excited to share a few new videos with you. But first, a little background. As you may know, I started working at Alphabet, Inc. just after finishing graduate school in 2020. I was on a team of amazing people that formed the core of what…
Symposium at The Master’s University
Math3ma — 3/15/2023
Recently on The Math3ma Institute’s blog, I announced an upcoming event that will be hosted at The Master’s University (TMU), which is a small private university in Santa Clarita, California. I wanted to briefly mention it here, too, in case it…
Sample Extraction from RLWE to LWE
Math ∩ Programming — 2/27/2023
In this article I’ll derive a trick used in FHE called sample extraction. In brief, it allows one to partially convert a ciphertext in the Ring Learning With Errors (RLWE) scheme to the Learning With Errors (LWE) scheme. Here are some other…
Google’s Fully Homomorphic Encryption Compiler — A Primer
Math ∩ Programming — 2/13/2023
Back in May of 2022 I transferred teams at Google to work on Fully Homomorphic Encryption (newsletter announcement). Since then I’ve been working on a variety of projects in the space, including being the primary maintainer on…
Formalizing invisible mathematics
Mathematics and Computation — 2/13/2023
I am at the Machine assisted proofs workshop at the UCLA Institute for Pure and Applied Mathematics, where I am about to give a talk on “Formalizing invisible mathematics”. Here are the slides with speaker notes and the video recording of the talk.
Exploring strange new worlds of mathematics
Mathematics and Computation — 2/10/2023
On February 10, 2023, I gave my Levi L. Conant Lectur Series talk “Exploring strange new worlds of mathematics”, at the math department of Worcester Polytechnic Institute. Here are the slides with speaker notes and the video recording of the talk.
A New Perspective of Entropy
Math3ma — 1/10/2023
Hello world! Last summer I wrote a short paper entitled “Entropy as a Topological Operad Derivation,” which describes a small but interesting connection between information theory, abstract algebra, and topology. I blogged about it here in June…
The Yoneda Lemma
Math3ma — 1/1/2023
Welcome to our third and final installment on the Yoneda lemma! In the past couple of weeks, we’ve slowly unraveled the mathematics behind the Yoneda perspective, i.e. the categorical maxim that an object is completely determined by its…
Estimating the Security of Ring Learning with Errors (RLWE)
Math ∩ Programming — 12/28/2022
This article was written by my colleague, Cathie Yun. Cathie is an applied cryptographer and security engineer, currently working with me to make fully homomorphic encryption a reality at Google. She’s also done a lot of cool stuff with zero…
Negacyclic Polynomial Multiplication
Math ∩ Programming — 12/9/2022
In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in…
Polynomial Multiplication Using the FFT
Math ∩ Programming — 11/16/2022
Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): “"”Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. “”” deg1 =…
Happy birthday, Dana!
Mathematics and Computation — 10/11/2022
Today Dana Scott is celebrating the 90th birthday today. Happy birthday, Dana! I am forever grateful for your kindness and the knowledge that I received from you. I hope to pass at least a part of it onto my students. On the occasion Steve Awodey…
Carnival of Mathematics #209
Math ∩ Programming — 10/2/2022
Welcome to the 209th Carnival of Mathematics! 209 has a few distinctions, including being the smallest number with 6 representations as a sum of 3 positive squares: $$\begin{aligned}209 &= 1^2 + 8^2 + 12^2 \\ &= 2^2 + 3^2 + 14^2 \\ &= 2^2 + 6^2 +…
Key Switching in LWE
Math ∩ Programming — 8/29/2022
Last time we covered an operation in the LWE encryption scheme called modulus switching, which allows one to switch from one modulus to another, at the cost of introducing a small amount of extra noise, roughly $\sqrt{n}$, where $n$ is the…
Modulus Switching in LWE
Math ∩ Programming — 7/16/2022
The Learning With Errors problem is the basis of a few cryptosystems, and a foundation for many fully homomorphic encryption (FHE) schemes. In this article I’ll describe a technique used in some of these schemes called modulus switching. In brief,…
One syntax to rule them all
Mathematics and Computation — 5/20/2022
I am at the Syntax and Semantics of Type Theory workshop in Stockholm, a kickoff meeting for WG6 of the EuroProofNet COST network, where I am giving a talk “One syntax to rule them all” based on joint work with Danel Ahman.
“Practical Math” Preview: Collect Sensitive Survey Responses Privately
Math ∩ Programming — 5/14/2022
This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production Software. Tip: Determine an aggregate statistic about a sensitive question, when survey respondents do not trust that their…
Cocktails
Math ∩ Programming — 4/1/2022
It’s April Cools! We’re taking back April Fools. When I was younger I had a strange relationship with alcohol, not because of any sort of trauma, but because I found it decidedly boring and disgusting to the taste. I didn’t drink in high school,…
Nix Substitution: the Way Forward
AlternativeBit — 3/31/2022
Abstract Nix and Guix have the unfortunate reputation to require a lot of bandwidth to distribute software. This reputation is sadly grounded. It seems like explicitly pointing to your dependencies comes with an overhead cost in terms of download…
Silent Duels—Constructing the Solution part 2
Math ∩ Programming — 3/24/2022
Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Silent Duels—Constructing the Solution part 1 Since it’s been three years since the last post in this series, and the reason for the…
My next book will be “Practical Math for Programmers”
Math ∩ Programming — 3/16/2022
tl;dr: I’m writing a new book, sign up for the announcements mailing list. I’ve written exactly zero new technical blog posts this year because I’ve been spending all my writing efforts on my next book, Practical Math for Programmers (PMFP,…
Stop Staring and Compute! Automorphism Groups of Rational Curves
Good Fibrations — 2/23/2022
Let’s compute the automorphism groups of some curves. Often presented as an insurmountable task, we must couragously go forward. There are many ways to do this! We will be using 3 different algorithms, so choose according to your taste. If you do…
Introducing The Math3ma Institute
Math3ma — 2/22/2022
Today I’m happy to share that the Math3ma platform has recently grown in a small yet personal way. This new endeavor is in its early stages, but it is one that is close to my heart and gives life to the reasons I started this blog six years ago. A…
Two new doctors!
Mathematics and Computation — 1/12/2022
Within a month two of my students defended their theses: Dr. Anja Petković Komel just before Christmas, and Dr. Philipp Haselwarter just yesterday. I am very proud of them. Congratulations!
The Gadget Decomposition in FHE
Math ∩ Programming — 12/11/2021
Lately I’ve been studying Fully Homomorphic Encryption, which is the miraculous ability to perform arbitrary computations on encrypted data without learning any information about the underlying message. It’s the most comprehensive private computing…
Chu are you?
mathematical fantasies — 11/6/2021
What the heck is a Chu space? And whatever it is, does it really belong with all the rich mathematical structures we know and love? Say you have some stuff. What can you do with it? Maybe it’s made of little pieces, and you can do a different thing…
Math3ma: Behind the Scenes (3B1B Podcast)
Math3ma — 11/1/2021
I recently had the pleasure of chatting with Grant Sanderson on the 3Blue1Brown podcast about a variety of topics, including what first drew me to math and physics, my time in graduate school, thoughts on category theory, basketball, and lots more….
Group Actions and Hashing Unordered Multisets
Math ∩ Programming — 10/14/2021
I learned of a neat result due to Kevin Ventullo that uses group actions to study the structure of hash functions for unordered sets and multisets. This piqued my interest because a while back a colleague asked me if I could think of any…
Language, Statistics, & Category Theory, Part 3
Math3ma — 9/27/2021
Welcome to the final installment of our mini-series on the new preprint “An Enriched Category Theory of Language,” joint work with John Terilla and Yiannis Vlassopoulos (https://arxiv.org/abs/2106.07890). Last time we discussed a way to assign sets…
Carnival of Mathematics #197
Math ∩ Programming — 9/1/2021
Welcome to the 197th Carnival of Mathematics! 197 is an unseemly number, as you can tell by the Wikipedia page which currently says that it has “indiscriminate, excessive, or irrelevant examples.” How deviant. It’s also a Repfigit, which means if…
Monotone Convergence Theorem
Math3ma — 8/16/2021
Fatou’s Lemma, the Monotone Convergence Theorem, and the Dominated Convergence Theorem are three major results in the theory of Lebesgue integration which, when given a sequence of functions ${f_n}$ answer the question, “When can I switch the…
Dominated Convergence Theorem
Math3ma — 8/16/2021
Fatou’s Lemma, the Monotone Convergence Theorem, and the Dominated Convergence Theorem are three major results in the theory of Lebesgue integration which, when given a sequence of functions ${f_n}$, answer the question, “When can I switch the…
The Borel-Cantelli Lemma
Math3ma — 8/16/2021
Today we’re chatting about the Borel-Cantelli Lemma. When I first came across this lemma, I struggled to understand what it meant “in English.” What does $\mu(\cup\cap E_k)=0$ really signify?? There’s a pretty simple explanation if $(X,\Sigma,\mu)$…
Entropy + Algebra + Topology = ?
Math3ma — 7/28/2021
Today I’d like to share some math connecting ideas from information theory, algebra, and topology. It’s all in a new paper I’ve recently uploaded to the arXiv (https://arxiv.org/abs/2107.09581), which describes a correspondence between Shannon…
Language, Statistics, & Category Theory, Part 2
Math3ma — 7/21/2021
Part 1 of this mini-series opened with the observation that language is an algebraic structure. But we also mentioned that thinking merely algebraically doesn’t get us very far. The algebraic perspective, for instance, is not sufficient to describe…
Language, Statistics, & Category Theory, Part 1
Math3ma — 7/7/2021
In the previous post I mentioned a new preprint that John Terilla, Yiannis Vlassopoulos, and I recently posted on the arXiv. In it, we ask a question motivated by the recent successes of the world’s best large language models: “What’s a mice…
A Nod to Non-Traditional Applied Math
Math3ma — 6/29/2021
What is applied mathematics? The phrase might bring to mind historical applications of analysis to physical problems, or something similar. I think that’s often what folks mean when they say “applied mathematics.” And yet there’s a much broader…
Linear Algebra for Machine Learning
Math3ma — 6/25/2021
The TensorFlow channel on YouTube recently uploaded a video I made on some elementary ideas from linear algebra and how they’re used in machine learning (ML). It’s a very nontechnical introduction — more of a bird’s-eye view of some basic concepts…
Warming Up to Enriched Category Theory, Part 2
Math3ma — 6/17/2021
Let’s jump right in to where we left off in part 1 of our warm-up to enriched category theory. If you’ll recall from last time, we saw that the set of truth values ${0, 1}$ and the unit interval $[0,1]$ and the nonnegative extended reals…
Searching for RH Counterexamples — Exploring Data
Math ∩ Programming — 6/14/2021
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up Productionizing In the last article we added a…
Warming Up to Enriched Category Theory, Part 1
Math3ma — 6/10/2021
It’s no secret that I like category theory. It’s a common theme on this blog, and it provides a nice lens through which to view old ideas in new ways — and to view new ideas in new ways! Speaking of new ideas, my coauthors and I are planning to…
The Fibonacci Sequence as a Functor
Math3ma — 6/8/2021
Over the years, the articles on this blog have spanned a wide range of audiences, from fun facts (Multiplying Non-Numbers), to undergraduate level (The First Isomorphism Theorem, Intuitively), to graduate level (What is an Operad?), to research…
TfE: What Kind of Computational Process is a Mind?
DEONTOLOGISTICS — 5/21/2021
Here’s a thread from the end of last year trying to reframe the core question of the computational theory of mind. I’m still not entirely happy with the arguments sketched here, but it’s a good introduction to the way I think we should articulate…
webcomic: re-search
Good Fibrations — 5/15/2021
Please enjoy my webcomic on what it feels like to run into a concept for the first time. I will be updating panel by panel, adding each one to this post as I make them. Here begins the adventures of Massey into the unknown.
TfE: The History of Metaphysics and Ontology
DEONTOLOGISTICS — 5/5/2021
If there’s a subject I’m officially an expert on, it’s what you might call the methodology of metaphysics: the question of what metaphysics is and how to go about it. I wrote my thesis on the question of Being in Heidegger’s work, trying to…
Meet the New Blog, Same as the Old Blog
DEONTOLOGISTICS — 5/3/2021
For those of you who haven’t already noticed, Deontologistics has undergone a bit of a redesign of late. It’s needed one for a while, for various reasons. But the thing that motivated me to finally do it was the realisation that this is the nexus…
Normal Service Will Resume Shortly
DEONTOLOGISTICS — 4/21/2021
Content Notes: Mental Health, Neurodiversity, Bipolar Disorder, Plurality/Multiplicity, TERFism, Personal Identity, Posthumanism. Length (~18K). PDF. 0. Vicious Cycles Another year, another extended absence. What a year though, right? Given how…
Regression and Linear Combinations
Math ∩ Programming — 3/29/2021
Recently I’ve been helping out with a linear algebra course organized by Tai-Danae Bradley and Jack Hidary, and one of the questions that came up a few times was, “why should programmers care about the concept of a linear combination?” For those…
Searching for RH Counterexamples — Productionizing
Math ∩ Programming — 3/6/2021
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up In the last article we rearchitected the…
Lost in the Labyrinth
DEONTOLOGISTICS — 2/25/2021
Content Notes: Amateur Genetics, Neurodiversity, Nick Land, NRx, Racism, Ignorance, Stupidity, Addiction As some people may have noticed, my experiments in using twitter as a platform for philosophical writing have become a bit more interactive of…
Searching for RH Counterexamples — Scaling Up
Math ∩ Programming — 2/16/2021
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Last time we made the audacious choice to remove primary…
Searching for RH Counterexamples — Performance Profiling
Math ∩ Programming — 2/2/2021
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker In the last article we ran into some performance issues with our deployed…
Searching for RH Counterexamples — Deploying with Docker
Math ∩ Programming — 1/4/2021
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded Integers In this article we’ll deploy the application on a server, so that it can search for RH…
Matrices as Tensor Network Diagrams
Math3ma — 12/29/2020
In the previous post, I described a simple way to think about matrices, namely as bipartite graphs. Today I’d like to share a different way to picture matrices—one which is used not only in mathematics, but also in physics and machine learning….
Limits and Colimits Part 3 (Examples)
Math3ma — 12/29/2020
Once upon a time, we embarked on a mini-series about limits and colimits in category theory. Part 1 was a non-technical introduction that highlighted two ways mathematicians often make new mathematical objects from existing ones: by taking a…
The Tensor Product, Demystified
Math3ma — 12/29/2020
Previously on the blog, we’ve discussed a recurring theme throughout mathematics: making new things from old things. Today, I’d like to focus on a particular way to build a new vector space from old vector spaces: the tensor product. This…
What is an Adjunction? Part 1 (Motivation)
Math3ma — 12/29/2020
Some time ago, I started a blog series introducing the basics of category theory (categories, functors, natural transformations). Today, adjunctions are now on the list! So, what is an adjunction? Here’s the start to a leisurely stroll through…
crumbs!
Math3ma — 12/29/2020
Recently I’ve been working on a dissertation proposal, which is sort of like a culmination of five years of graduate school (yay). The first draft was rough, but I sent it to my advisor anyway. A few days later I walked into his office, smiled, and…
Viewing Matrices & Probability as Graphs
Math3ma — 12/29/2020
Today I’d like to share an idea. It’s a very simple idea. It’s not fancy and it’s certainly not new. In fact, I’m sure many of you have thought about it already. But if you haven’t—and even if you have!—I hope you’ll take a few minutes to enjoy it…
A First Look at Quantum Probability, Part 1
Math3ma — 12/29/2020
In this article and the next, I’d like to share some ideas from the world of quantum probability. The word “quantum” is pretty loaded, but don’t let that scare you. We’ll take a first—not second or third—look at the subject, and the only…
A First Look at Quantum Probability, Part 2
Math3ma — 12/29/2020
Welcome back to our mini-series on quantum probability! Last time, we motivated the series by pondering over a thought from classical probability theory, namely that marginal probability doesn’t have memory. That is, the process of summing over of…
What is an Adjunction? Part 2 (Definition)
Math3ma — 12/29/2020
Last time I shared a light introduction to adjunctions in category theory. As we saw then, an adjunction consists of a pair of opposing functors $F$ and $G$ together with natural transformations $\text{id}\to\ GF$ and $FG\to\text{id}$ that interact…
What is an Adjunction? Part 3 (Examples)
Math3ma — 12/29/2020
Welcome to the last installment in our mini-series on adjunctions in category theory. We motivated the discussion in Part 1 and walked through formal definitions in Part 2. Today I’ll share some examples. In Mac Lane’s well-known words, “adjoint…
crumbs!
Math3ma — 12/29/2020
There are a couple of questions that I’m asked quite frequently these days: “How far along are you in graduate school?” “What’s your research about anyways?” I created Math3ma precisely for my time in graduate school, so I thought it’d be…
Applied Category Theory 2020
Math3ma — 12/29/2020
Hi all, just ducking in to help spread the word: the annual applied category theory conference (ACT2020) is taking place remotely this summer! Be sure to check out the conference website for the latest updates. As you might know, I was around for…
Topology: A Categorical Approach
Math3ma — 12/29/2020
I’ve been collaborating on an exciting project for quite some time now, and today I’m happy to share it with you. There is a new topology book on the market! Topology: A Categorical Approach is a graduate-level textbook that presents basic topology…
At the Interface of Algebra and Statistics
Math3ma — 12/29/2020
I’m happy to share that I’ve successfully defended my PhD thesis, and my dissertation—”At the Interface of Algebra and Statistics”—is now available online at arXiv:2004.05631. In a few words, my thesis uses basic tools from quantum physics to…
What’s Next? (An Update)
Math3ma — 12/29/2020
Before introducing today’s post, I’d like to first thank everyone who’s reached out to me about my thesis and video posted last week. Thanks! I appreciate all the generous feedback. Now onto the topic of the day: I’d like to share an update about…
Language Modeling with Reduced Densities
Math3ma — 12/29/2020
Today I’d like to share with you a new paper on the arXiv [2007.03834]—my latest project in collaboration with mathematician Yiannis Vlassopoulos (Tunnel, IHES). In it, We present a framework for modeling words, phrases, and longer expressions in a…
Topology Book Launch
Math3ma — 12/29/2020
This is the official launch week of our new book, “Topology: A Categorical Approach,” which is now available for purchase! We are also happy to offer a free open access version through MIT Press at topology.mitpress.mit.edu. [Read more on Math3ma!]
Finitely Generated Modules Over a PID
Math3ma — 12/12/2020
We know what it means to have a module $M$ over a (commutative, say) ring $R$. We also know that if our ring $R$ is actually a field, our module becomes a vector space. But what happens if $R$ is “merely” a PID? Answer: A lot. Today we’ll look at a…
Optimization Models for Subset Cover
Math ∩ Programming — 10/20/2020
In a recent newsletter article I complained about how researchers mislead about the applicability of their work. I gave SAT solvers as an example. People provided interesting examples in response, but what was new to me was the concept of SMT…
What do Polygons and Galois Theory Have in Common?
Math3ma — 10/15/2020
Galois Theory is all about symmetry. So, perhaps not surprisingly, symmetries found among the roots of polynomials (via Galois theory) are closely related to symmetries of polygons in the plane (via geometry). In fact, the two are highly analogous!
Searching for RH Counterexamples — Unbounded Integers
Math ∩ Programming — 10/13/2020
We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search strategies In the last article, we improved our naive search from “try all positive integers” to enumerate a subset of integers…
Searching for RH Counterexamples — Search Strategies
Math ∩ Programming — 9/28/2020
We’re glibly searching for counterexamples to the Riemann Hypothesis, to trick you into learning about software engineering principles. In the first two articles we configured a testing framework and showed how to hide implementation choices behind…
Searching for RH Counterexamples — Adding a Database
Math ∩ Programming — 9/11/2020
In the last article we set up pytest for a simple application that computes divisor sums $ \sigma(n)$ and tries to disprove the Riemann Hypothesis. In this post we’ll show how to extend the application as we add a database dependency. The database…
Searching for RH Counterexamples — Setting up Pytest
Math ∩ Programming — 9/11/2020
Some mathy-programmy people tell me they want to test their code, but struggle to get set up with a testing framework. I suspect it’s due to a mix of: There are too many choices with a blank slate. Making slightly wrong choices early on causes…
Taylor Series and Accelerometers
Math ∩ Programming — 7/26/2020
In my book, A Programmer’s Introduction to Mathematics, I describe the Taylor Series as a “hammer for every nail.” I learned about another nail in the design of modern smartphone accelerometers from “Eight Amazing Engineering Stories” by Hammack,…
Visual Linear Logic
mathematical fantasies — 6/8/2020
What even is logic anyway? Logic is about what patterns of thought are valid. There are different kinds of logic for thinking about different kinds of things. Classical logic is for thinking about truth. Intuitionistic logic is for thinking about…
Contextual Symbols in Math
Math ∩ Programming — 5/22/2020
In my book I discuss the importance of context in reading and writing mathematics. An early step in becoming comfortable with math is deciphering the syntax of mathematical expressions. Another is in connecting the symbols to their semantic…
Musings on A New Interface for Mathematics
Math ∩ Programming — 5/17/2020
This essay is a slightly modified version of the closing chapter of A Programmer’s Introduction to Mathematics. We are no longer constrained by pencil and paper. The symbolic shuffle should no longer be taken for granted as the fundamental…
Second Edition of A Programmer’s Introduction to Mathematics
Math ∩ Programming — 5/17/2020
The Second Edition of A Programmer’s Introduction to Mathematics is now available on Amazon. The second edition includes a multitude of fixes to typos and some technical errata, thanks to my readers who submitted over 200 errata. Readers who…
The Yoneda Perspective
Math3ma — 4/21/2020
In the words of Dan Piponi, it “is the hardest trivial thing in mathematics.” The nLab catalogues it as “elementary but deep and central,” while Emily Riehl nominates it as “arguably the most important result in category theory.” Yet as Tom…
Ways to Show a Group is Abelian
Math3ma — 2/7/2020
After some exposure to group theory, you quickly learn that when trying to prove a group $G$ is abelian, checking if $xy=yx$ for arbitrary $x,y$ in $G$ is not always the most efficient - or helpful! - tactic. Here is a (not comprehensive) running…
What is a Natural Transformation? Definition and Examples
Math3ma — 1/30/2020
I hope you have enjoyed our little series on basic category theory. (I know I have!) This week we’ll close out by chatting about natural transformations which are, in short, a nice way of moving from one functor to another. If you’re new to this…
The Yoneda Embedding
Math3ma — 1/29/2020
Last week we began a discussion about the Yoneda lemma. Though rather than stating the lemma (sans motivation), we took a leisurely stroll through an implication of its corollaries - the Yoneda perspective, as we called it: An object is completely…
The Communicative Value of Using Git Well
Math ∩ Programming — 1/14/2020
Recently my employer (Google) forced me to switch to Mercurial instead of my usual version control system, git. The process of switching sparked a few discussions between me and my colleagues about the value of various version control systems. A…
Hecke orbits and Homotopy
Good Fibrations — 1/7/2020
I thought it might be of interest to homotopy theorists to learn how the Lubin-Tate action is relevant in the Hecke orbit conjecture. Here is a beginner friendly summary. heckeorbitshomotopy
TfE: Varieties of Rule Following
DEONTOLOGISTICS — 12/27/2019
Here’s a thread from a few weeks ago, explaining an interesting but underexplored overlap between a theoretical problem in philosophy and a practical problem in computer science: Okay, it looks like I’m going to have to explain my take on the…
Rational Canonical Form: Example #1
Math3ma — 12/27/2019
Last time we discussed the rational canonical form (RCF) of a linear transformation, and we mentioned that any two similar linear transformations have the same RCF. It’s this fact which allows us to classify distinct linear transformations on a…
TfE: Turing and Hegel
DEONTOLOGISTICS — 12/21/2019
Here’s a thread on something I’ve been thinking about for a few years now. I can’t say I’m the only one thinking about this convergence, but I like to think I’m exploring it from a slightly different direction. I increasingly think the Turing test…
Compact + Hausdorff = Normal
Math3ma — 12/3/2019
The notion of a topological space being Hausdorff or normal identifies the degree to which points or sets can be “separated.” In a Hausdorff space, it’s guaranteed that if you pick any two distinct points in the space – say $x$ and $y$ – then you…
A Good Year for “A Programmer’s Introduction to Mathematics”
Math ∩ Programming — 12/1/2019
A year ago today I self-published “A Programmer’s Introduction to Mathematics” (PIM). In this short note I want to describe the success it’s had, summarize the complaints of some readers and the praise of others, and outline what’s next. Since…
Honda, Taira, On the Formal Structure of the Jacobian Variety of the Fermat Curve over a (p)-adic Integer Ring
Good Fibrations — 11/26/2019
This paper of Honda was very hard for me to track down. I found it in a retired library volume in a thrift store in England. It was not previously available digitally. Hopefully, this digital copy will make it easier for others to enjoy Honda’s…
TfE: From Cyberpunk to Infopunk
DEONTOLOGISTICS — 11/25/2019
I have a somewhat tortured relationship to literary and cultural criticism. I think that, like most people, some of my most complex and nuanced opinions are essentially aesthetic. I’ve written quite a lot about the nature of art, aesthetics, and…
TfE: Incompetence, Malice, and Evil
DEONTOLOGISTICS — 11/5/2019
Here’s a thread from Saturday that seemed to be quite popular. It explains a saying that I’ve found myself reaching for a lot recently, using some other ideas I’ve been developing in the background on the intersection between philosophy of action,…
TfE: Information and Energy
DEONTOLOGISTICS — 11/1/2019
Here’s another bit of spontaneous Facebook philosophy, responding to a post by my friend Carl Sachs. The following thoughts are largely inspired by Samson Abramsky‘s majestic ‘Information, Processes and Games‘. So, say I’ve got a biological…
crumbs!
Math3ma — 8/19/2019
One of my students recently said to me, “I’m not good at math because I’m really slow.” Right then and there, she had voiced what is one of many misconceptions that folks have about math. But friends, speed has nothing to do with one’s ability to…
Silent Duels—Constructing the Solution part 1
Math ∩ Programming — 6/30/2019
Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Last time we waded into Restrepo’s silent duel paper. You can see the original and my re-typeset version on Github along with all of the…
Limits and Colimits, Part 2 (Definitions)
Math3ma — 6/29/2019
Welcome back to our mini-series on categorical limits and colimits! In Part 1 we gave an intuitive answer to the question, “What are limits and colimits?” As we saw then, there are two main ways that mathematicians construct new objects from a…
Math Versus Dirty Data
Math ∩ Programming — 6/8/2019
At Google, our organization designs, owns, and maintains a number of optimization models that automate the planning of Google’s datacenter growth and health. As is pretty standard in supply chain optimization and planning, these models are often…
Snippets of Mathematical Candor
Math3ma — 6/7/2019
A while ago I wrote a post in response to a great Slate article reminding us that math - like writing - isn’t something that anyone is good at without (at least a little!) effort. As the article’s author put it, “no one is born knowing the axiom of…
Constructing the Tensor Product of Modules
Math3ma — 5/15/2019
Today we talk tensor products. Specifically this post covers the construction of the tensor product between two modules over a ring. But before jumping in, I think now’s a good time to ask, “What are tensor products good for?” Here’s a simple…
The Integral Domain Hierarchy, Part 2
Math3ma — 5/15/2019
In any area of math, it’s always good idea to keep a few counterexamples in your back pocket. This post continues part 1 with examples/non-examples from some of the different subsets of integral domains.
Sperner’s lemma
mathematical fantasies — 5/13/2019
I found a proof of Sperner’s lemma that I am quite satisfied with a few months ago. I’ll repeat the proof here, but more importantly I’d like to share my thought process that lead to the proof. What is Sperner’s lemma? Look at the triangle below….
Commutative Diagrams Explained
Math3ma — 5/6/2019
Have you ever come across the words “commutative diagram” before? Perhaps you’ve read or heard someone utter a sentence that went something like, “For every [bla bla] there existsa [yadda yadda] such thatthe following diagram commutes.” and perhaps…
A Working Mathematician’s Guide to Parsing
Math ∩ Programming — 4/20/2019
Our hero, a mathematician, is writing notes in LaTeX and needs to convert it to a format that her blog platform accepts. She’s used to using dollar sign delimiters for math mode, but her blog requires ( ) and [ ]. Find-and-replace fails because…
Overview of the Classic Theory of p-Divisible groups
Good Fibrations — 4/10/2019
Here are the texed notes for my 1 hour oberwolfach talk (the key thing I left out is Cartier duality). I included Manin’s original approach, and remark on some details I find left out of most sources.
Comparing Topologies
Math3ma — 4/5/2019
It’s possible that a set $X$ can be endowed with two or more topologies that are comparable. Over the years, mathematicians have used various words to describe the comparison: a topology $\tau_1$ is said to be coarser than another topology…
Silent Duels—Parsing the Construction
Math ∩ Programming — 1/28/2019
Last time we discussed the setup for the silent duel problem: two players taking actions in $ [0,1]$, player 1 gets $ n$ chances to act, player 2 gets $ m$, and each knows their probability of success when they act. The solution is in a paper of…
A Math Blog? Say What?
Math3ma — 1/24/2019
Yes! I’m writing about math. No! Don’t close your browser window. Hear me out first… I know very well that math has a bad rap. It’s often taught or thought of as a dry, intimidating, unapproachable, completely boring,…
Limits and Colimits, Part 1 (Introduction)
Math3ma — 1/24/2019
I’d like to embark on yet another mini-series here on the blog. The topic this time? Limits and colimits in category theory! But even if you’re not familiar with category theory, I do hope you’ll keep reading. Today’s post is just an informal,…
Announcing Applied Category Theory 2019
Math3ma — 1/9/2019
Hi everyone. Here’s a quick announcement: the Applied Category Theory 2019 school is now accepting applications! As you may know, I participated in ACT2018, had a great time, and later wrote a mini-book based on it. This year, it’s happening again…
Notes on Applied Category Theory
Math3ma — 1/6/2019
Have you heard the buzz? Applied category theory is gaining ground! But, you ask, what is applied category theory? Upon first seeing those words, I suspect many folks might think either one of two thoughts: 1. Applied category theory? Isn’t that an…
Silent Duels and an Old Paper of Restrepo
Math ∩ Programming — 12/31/2018
Two men start running at each other with loaded pistols, ready to shoot! It’s a foggy morning for a duel. Newton and Leibniz have decided this macabre contest is the only way to settle their dispute over who invented Calculus. Each pistol is fitted…
Automorphisms of the Jacobian
Good Fibrations — 12/31/2018
Here, (A) is any abelian variety. This post consists of the backstory of my latest paper with Dami Lee and something interesting I learned about the relationship between the size of (Aut(A)), and the number of principal polarizations (A) has.
Fiber Bundles of Formal Disks
Good Fibrations — 12/31/2018
Here is an incomplete proof that varieties are fiber bundles of formal disks over their deRham Stacks. The fact makes intuitive sense, the deRham stack is the variety without infinitesimal data, and then by adding the infinitesimal data (formal…
A Programmer’s Introduction to Mathematics
Math ∩ Programming — 12/1/2018
For the last four years I’ve been working on a book for programmers who want to learn mathematics. It’s finally done, and you can buy it today. The website for the book is pimbook.org, which has purchase links—paperback and ebook—and a preview of…
Operator Norm, Intuitively
Math3ma — 11/23/2018
| If $X$ and $Y$ are normed vector spaces, a linear map $T:X\to Y$ is said to be bounded if $|T|< \infty$ where $$|T|=\sup_{\underset{x\neq 0}{x\in X}}\left{\frac{ | T(x) | }{ | x | }\right}.$$ (Note that $ | T(x) | $ is the norm in $Y$ whereas $ | x | $ is… |
“Up to Isomorphism”?
Math3ma — 11/23/2018
Up to isomorphism” is a phrase that seems to get thrown around a lot without ever being explained. Simply put, we say two groups (or any other algebraic structures) are the same “up to isomorphism” if they’re isomorphic! In other words, they share…
Borel-Cantelli Lemma (Pictorially)
Math3ma — 11/23/2018
The Borel-Cantelli Lemma says that if $(X,\Sigma,\mu)$ is a measure space with $\mu(X)<\infty$ and if ${E_n}{n=1}^\infty$ is a sequence of measurable sets such that $\sum_n\mu(E_n)<\infty$, then $$\mu\left(\bigcap{n=1}^\infty…
English is Not Commutative
Math3ma — 11/23/2018
Here’s another unspoken rule of mathematics: English doesn’t always commute! Word order is important…
What’s a Transitive Group Action?
Math3ma — 11/23/2018
Let a group $G$ act on a set $X$. The action is said to be transitive if for any two $x,y\in X$ there is a $g\in G$ such that $g\cdot x=y$. This is equivalent to saying there is an $x\in X$ such that $\text{orb}(x)=X$, i.e. there is exactly one…
Need to Prove Your Ring is NOT a UFD?
Math3ma — 11/23/2018
You’re given a ring $R$ and are asked to show it’s not a UFD. Where do you begin? One standard trick is to apply the Rational Roots Theorem….
Why are Noetherian Rings Special?
Math3ma — 11/23/2018
In short, “Noetherian-ness” is a property which generalizes “PID-ness.” As Keith Conrad so nicely puts it, “The property of all ideals being singly generated is often not preserved under common ring-theoretic constructions (e.g. $\mathbb{Z}$ is a…
One Unspoken Rule of Algebra
Math3ma — 11/23/2018
Here’s an algebra tip! Whenever you’re asked to prove \(A/B\cong C\) where $A,B,C$ are groups, rings, fields, modules, etc., mostly likely the The First Isomorphism Theorem involved!
Completing a Metric Space, Intuitively
Math3ma — 11/23/2018
An incomplete metric space is very much like a golf course: it has a lot of missing points!
One Unspoken Rule of Measure Theory
Math3ma — 11/23/2018
Here’s a measure theory trick: when asked to prove that a set of points in $\mathbb{R}$ (or some measure space $X$) has a certain property, try to show that the set of points which does NOT have that property has measure 0! This technique is used…
Learning How to Learn Math
Math3ma — 11/18/2018
Once upon a time, while in college, I decided to take my first intro-to-proofs class. I was so excited. “This is it!” I thought, “now I get to learn how to think like a mathematician.” You see, for the longest time, my mathematical upbringing was…
Ex-Hack: a Haskell Example-based Documentation
AlternativeBit — 11/15/2018
Abstract Ex-Hack is an example-based documentation automatically generated using the packages posted on Stackage. There’s a live demo here. We’ve just released the alpha version; you can have a look to the code here. We are actively looking for new…
Portrait Practice
Good Fibrations — 11/13/2018
Ultimate Writer: an Open Digital Typewriter
AlternativeBit — 10/17/2018
TL;DR: A digital typewriter based on a Raspberry Pi and an E-Ink screen. The code/build instructions are available on GitHub. I am easily distracted. This is both a blessing and a curse. On one hand, I can deal with a large amount of boredom…
Is the Square a Secure Polygon?
Math3ma — 10/13/2018
In this week’s episode of PBS Infinite Series, I shared the following puzzle: Consider a square in the xy-plane, and let A (an “assassin”) and T (a “target”) be two arbitrary-but-fixed points within the square. Suppose that the square behaves like…
Topological Magic: Infinitely Many Primes
Math3ma — 10/7/2018
A while ago, I wrote about the importance of open sets in topology and how the properties of a topological space $X$ are highly dependent on these special sets. In that post, we discovered that the real line $\mathbb{R}$ can either be compact or…
What is a Category? Definition and Examples
Math3ma — 9/20/2018
As promised, here is the first in our triad of posts on basic category theory definitions: categories, functors, and natural transformations. If you’re just now tuning in and are wondering what is category theory, anyway? be sure to follow the link…
Two Tricks Using Eisenstein’s Criterion
Math3ma — 9/11/2018
Today we’re talking about Eisenstein’s (not Einstein’s!) Criterion - a well-known test to determine whether or not a polynomial is irreducible. In particular, we’ll consider two examples where a not-so-obvious trick is needed in order to apply the…
“One-Line” Proof: Fundamental Group of the Circle
Math3ma — 9/11/2018
Once upon a time I wrote a six-part blog series on why the fundamental group of the circle is isomorphic to the integers. (You can read it here, though you may want to grab a cup of coffee first.) Last week, I shared a proof* of the same result. In…
The Fundamental Group of the Circle, Part 6
Math3ma — 9/11/2018
Welcome to the final post in a six-part series where we prove that the fundamental group of the circle $\pi_1(S^1)$ is isomorphic to $\mathbb{Z}$. Today we prove two lemmas (the path- and homotopy-lifting properties) that were used in parts four…
#TrustYourStruggle
Math3ma — 9/11/2018
If you’ve been following this blog for a while, you’ll know that I have strong opinions about the misconception that “math is only for the gifted.” I’ve written about the importance of endurance and hard work several times. Naturally, these…
What’s a Quotient Group, Really? Part 1
Math3ma — 9/11/2018
I realize that most of my posts for the past, er, few months have been about some pretty hefty duty topics. Today, I’d like to dial it back a bit and chat about some basic group theory! So let me ask you a question: When you hear the words…
The Fundamental Group of the Real Projective Plane
Math3ma — 9/11/2018
The goal of today’s post is to prove that the fundamental group of the real projective plane, is isomorphic to $\mathbb{Z}/2\mathbb{Z}$ And unlike our proof for the fundamental group of the circle, today’s proof is fairly short, thanks to the van…
Topology vs. “A Topology” (cont.)
Math3ma — 9/11/2018
This blog post is a continuation of today’s episode on PBS Infinite Series, “Topology vs. ‘a’ Topology.” My hope is that this episode and post will be helpful to anyone who’s heard of topology and thought, “Hey! This sounds cool!” then picked up a…
The Fundamental Group of the Circle, Part 4
Math3ma — 9/11/2018
Welcome to part four of a six-part series where we prove that the fundamental group of the circle $\pi_1(S^1)$ is isomorphic to $\mathbb{Z}$. In this post we prove that our homomorphism from $\mathbb{Z}$ to $\pi_1(S^1)$ is surjective. The proof…
Math Emojis
Math3ma — 9/11/2018
☺️ I love math 😀 It’s so cool.
Baire Category & Nowhere Differentiable Functions (Part Two)
Math3ma — 9/11/2018
Welcome to part two of our discussion on Baire’s Category Theorem. Today we’ll sketch the proof that we can find a continuous function on $[0,1]$ which is nowhere differentiable.
What is an Operad? Part 2
Math3ma — 9/11/2018
Last week we introduced the definition of an operad: it’s a sequence of sets or vector spaces or topological spaces or most anything you like (whose elements we think of as abstract operations), together with composition maps and a way to permute…
What is an Operad? Part 1
Math3ma — 9/11/2018
If you browse through the research of your local algebraist, homotopy theorist, algebraic topologist or―well, anyone whose research involves an operation of some type, you might come across the word “operad.” But what are operads? And what are they…
On Connectedness, Intuitively
Math3ma — 9/11/2018
Today’s post is a bit of a ramble, but my goal is to uncover the intuition behind one of the definitions of a connected topological space. Ideally, this is just a little tidbit I’d like to stash in The Back Pocket. But as you can tell already, the…
A Ramble About Qualifying Exams
Math3ma — 9/11/2018
Today I’m talking about about qualifying exams! But no, I won’t be dishing out advice on preparing for these exams. Tons of excellent advice is readily available online, so I’m not sure I can contribute much that isn’t already out there. However,…
Brouwer’s Fixed Point Theorem (Proof)
Math3ma — 9/11/2018
Today I’d like to talk about Brouwer’s Fixed Point Theorem. Literally! It’s the subject of this week’s episode on PBS Infinite Series. Brouwer’s Fixed Point Theorem is a result from topology that says no matter how you stretch, twist, morph, or…
Motivation for the Tensor Product
Math3ma — 9/11/2018
In general, if $F$ is a field and $V$ is a vector space over $F$, the tensor product answers the question “How can I define scalar multiplication on $V$ by some larger field which contains $F$?” (Of course this holds if we replace the word “field”…
The Pseudo-Hyperbolic Metric and Lindelöf’s Inequality
Math3ma — 9/11/2018
In this post, we define the pseudo-hyperbolic metric on the unit disc in ℂ and prove it does indeed satisfy the conditions of a metric.
A Group and Its Center, Intuitively
Math3ma — 9/11/2018
Last week we took an intuitive peek into the First Isomorphism Theorem as one example in our ongoing discussion on quotient groups. Today we’ll explore another quotient that you’ve likely come across, namely that of a group by its center.
Good Reads: Real Analysis by N. L. Carothers
Math3ma — 9/11/2018
Have you been on the hunt for a good introductory-level real analysis book? Look no further! The underrated Real Analysis by N. L. Carothers is, in my opinion, one of the best out there.
What is a Functor? Definitions and Examples, Part 2
Math3ma — 9/11/2018
Continuing yesterday’s list of examples of functors, here is Example #3 (the chain rule from multivariable calculus), Example #4 (contravariant functors), and Example #5 (representable functors).
Resources for Intro-Level Graduate Courses
Math3ma — 9/11/2018
In recent months, several of you have asked me to recommend resources for various subjects in mathematics. Well, folks, here it is! I’ve finally rounded up a collection of books, PDFs, videos, and websites that I found helpful while studying for my…
What is Galois Theory Anyway?
Math3ma — 9/11/2018
Perhaps you’ve heard of Évariste Galois? (Pronounced “GAL-wah.”) You know, the French mathematician who died tragically in 1832 in a duel at the tender age of 20? (Supposedly over a girl! C’est romantique, n’est-ce pas?) Well, today we’re taking a…
Absolute Continuity (Part One)
Math3ma — 9/11/2018
There are two definitions of absolute continuity out there. One refers to an absolutely continuous function and the other to an absolutely continuous measure. And although the definitions appear unrelated, they are in fact very much related, linked…
Absolute Continuity (Part Two)
Math3ma — 9/11/2018
There are two definitions of absolute continuity out there. One refers to an absolutely continuous function and the other to an absolutely continuous measure. And although the definitions appear unrelated, they are in fact very much related, linked…
crumbs!
Math3ma — 9/11/2018
One day while doing a computation on the board in front of my students, I accidentally wrote 1 + 1 = 1. (No idea why.) Student: Um, don’t you mean 1 + 1 = 2? Me (embarrassed): Oh right, thanks. [Erases mistake. Pauses.] Wait. Is there a universe in…
Good Reads: Love and Math
Math3ma — 9/11/2018
Love and Math by Edward Frenkel is an excellent book about the hidden beauty and elegance of mathematics. It is primarily about Frenkel’s work on the Langlands Program (a sort of grand unified theory of mathematics) and its recent connections to…
crumbs!
Math3ma — 9/11/2018
Not too long ago, my college-algebra students and I were chatting about graphing polynomials. At one point during our lesson, I quickly drew a smooth, wavy curve on the board and asked, “How many roots would a polynomial with this graph have? Five?…
The Pseudo-Hyperbolic Metric and Lindelöf’s Inequality (cont.)
Math3ma — 9/11/2018
Last time we proved that the pseudo-hyperbolic metric on the unit disc in ℂ is indeed a metric. In today’s post, we use this fact to verify Lindelöf’s inequality which says, “Hey! Want to apply Schwarz’s Lemma but don’t know if your function fixes…
Hanabi: a card game for logicians
Math ∩ Programming — 8/10/2018
Mathematics students often hear about the classic “blue-eyed islanders” puzzle early in their career. If you haven’t seen it, read Terry Tao’s excellent writeup linked above. The solution uses induction and the idea of common knowledge—I know X,…
Loading a Cabal module in the GHC API
AlternativeBit — 8/8/2018
If you plan to build some Haskell tooling or any kind of static code analyzer, chances are you’ll need to use the GHC API at some point. While loading a simple module into GHC’s API is quite trivial and well documented, loading complex modules…
Visualizing an Assassin Puzzle
Math ∩ Programming — 7/24/2018
Over at Math3ma, Tai-Danae Bradley shared the following puzzle, which she also featured in a fantastic (spoiler-free) YouTube video. If you’re seeing this for the first time, watch the video first. Consider a square in the xy-plane, and let A (an…
Silver Searcher: Useful Regexes for a Haskell Code-Base
AlternativeBit — 7/22/2018
| TL;DR I use 4 Perl Regex patterns most of the time when it comes to search some Haskell code: Functions: “\b\b[ \t\n]+::” Types: “(data | newtype | type)(\ +)\b\b” TypeClasses: “class(\ +)(.)(=>)(\ *)\b\b” Constructors: “|[\t\ ]+\b\b” I… |
For mathematicians, = does not mean equality
Math ∩ Programming — 4/13/2018
Every now and then I hear some ridiculous things about the equals symbol. Some large subset of programmers—perhaps related to functional programmers, perhaps not—seem to think that = should only and ever mean “equality in the mathematical sense.”…
A parlor trick for SET
Math ∩ Programming — 3/25/2018
Tai-Danae Bradley is one of the hosts of PBS Infinite Series, a delightful series of vignettes into fun parts of math. The video below is about the same of SET, a favorite among mathematicians. Specifically, Tai-Danae explains how SET cards lie in…
Earthmover Distance
Math ∩ Programming — 3/5/2018
Problem: Compute distance between points with uncertain locations (given by samples, or differing observations, or clusters). For example, if I have the following three “points” in the plane, as indicated by their colors, which is closer, blue to…
Please, Keep your Blog Light
AlternativeBit — 1/24/2018
TL;DR: keeping your blog lightweight is important, I show you how to design a blog fitting in less than 10kB. You’re already convinced weight really matters when it comes to web pages? You can skip the introduction and directly see how you can…
NP-hard does not mean hard
Math ∩ Programming — 12/29/2017
When NP-hardness pops up on the internet, say because some silly blogger wants to write about video games, it’s often tempting to conclude that the problem being proved NP-hard is actually very hard! “Scientists proved Super Mario is NP-hard? I…
Bracket: a Tale of Partially Applied Functions
AlternativeBit — 11/29/2017
TL;DR In this post, we describe how we can use partially applied functions as a design building block though the study of a practical example: the bracket function. I’ll use the Haskell programming language to illustrate this post. Just keep in…
Binary Search on Graphs
Math ∩ Programming — 11/8/2017
Binary search is one of the most basic algorithms I know. Given a sorted list of comparable items and a target item being sought, binary search looks at the middle of the list, and compares it to the target. If the target is larger, we repeat on…
Writing a Twitch Overlay using Haskell
AlternativeBit — 10/21/2017
I have been watching Jessica’s Mak streams lately. She is an indie game developper, but most of all, she has a kick ass overlay that shows what she is typing in real time. I wanted the same one, I made it using Haskell, Gloss and Chipmunk via the…
Wireguard-Haskell: Getting Started
AlternativeBit — 10/16/2017
Why Starting this Project? After finishing DobadoBots, I was looking for a Haskell project in which I could be confronted with some performance and parallelism problems. Wireguard seemed to be the perfect project for that. At the time, no userspace…
DobadoBots: Project Wrap Up
AlternativeBit — 9/28/2017
Yet another post about DobadoBots: my programming video-game. Right, let’s face it: it is done for two months now, this blog post is long overdue! The video-game is now completely playable, I reached the MVP stage. Here’s a short video presenting…
Linear Programming and Healthy Diets — Part 2
Math ∩ Programming — 9/24/2017
Previously in this series: Linear programming and healthy diets — Part 1 Linear programing and the simplex algorithm Foods of the Father My dad’s an interesting guy. Every so often he picks up a health trend and/or weight loss goal that would make…
DobadoBots: Writing a Text Editor
AlternativeBit — 9/4/2017
Yup, yet another post on my programming videogame: Dobadobots. Today, we are going to dig into the editor’s implementation. Motivations I wanted the game to be as enjoyable as possible, I wanted a quick write/feedback loop….
Notes on Math and Gerrymandering
Math ∩ Programming — 8/14/2017
Last week I was in Boston for the Geometry of Redistricting workshop. It was an optimistic gathering of over 500 mathematicians, computer scientists, lawyers, policy makers, teachers, and interested people of all stripes. There was a ton of…
Boolean Logic in Polynomials
Math ∩ Programming — 7/24/2017
Problem: Express a boolean logic formula using polynomials. I.e., if an input variable $ x$ is set to $ 0$, that is interpreted as false, while $ x=1$ is interpreted as true. The output of the polynomial should be 0 or 1 according to whether the…
DobadoBots: Implementing the Parser
AlternativeBit — 7/20/2017
Lately, I have been working on a video-game called DobadoBots. This game is about programming a robot’s artificial intelligence to solve mazes. The robot is materialized by a white triangle. The goal is to reach the…
DobadoBots: Specifying the Language
AlternativeBit — 6/25/2017
Lately, I have been working on a video-game called DobadoBots. This game is about programming a robot’s articial intelligence to solve mazes. The robot is materialized by a white triangle. The goal is to reach the objective…
Mathematical Genealogy
Math ∩ Programming — 6/22/2017
As a fun side project to distract me from my abysmal progress on my book, I decided to play around with the math genealogy graph! For those who don’t know, since 1996, mathematicians, starting with the labor of Harry Coonce et al, have been…
One Year of FOSS
AlternativeBit — 6/18/2017
One Year of FOSS Hello internet friends, long time no see. After doing a total revamp of this weblog, I think it is finally time to explain what’s happening in my life. Two months ago, I decided to quit my job. I was tired of Paris’s pollution. I…
Duality for the SVM
Math ∩ Programming — 6/12/2017
This post is a sequel to Formulating the Support Vector Machine Optimization Problem. The Karush-Kuhn-Tucker theorem Generic optimization problems are hard to solve efficiently. However, optimization problems whose objective and constraints have…
Formulating the Support Vector Machine Optimization Problem
Math ∩ Programming — 6/5/2017
The hypothesis and the setup This blog post has an interactive demo (mostly used toward the end of the post). The source for this demo is available in a Github repository. Last time we saw how the inner product of two vectors gives rise to a…
The Inner Product as a Decision Rule
Math ∩ Programming — 5/22/2017
The standard inner product of two vectors has some nice geometric properties. Given two vectors $ x, y \in \mathbb{R}^n$, where by $ x_i$ I mean the $ i$-th coordinate of $ x$, the standard inner product (which I will interchangeably call the dot…
Testing Polynomial Equality
Math ∩ Programming — 4/24/2017
| Problem: Determine if two polynomial expressions represent the same function. Specifically, if $ p(x_1, x_2, \dots, x_n)$ and $ q(x_1, x_2, \dots, x_n)$ are a polynomial with inputs, outputs and coefficients in a field $ F$, where $ | F | $ is… |
Real World Haskell Chapter 9 Solutions
AlternativeBit — 4/4/2017
Exercise P.221 Is the order in which we call bracket and handle important? Yup, it is pretty important: the code executed during the in-between statement of bracket still can raise an exception. We do not want our application to crash in case of an…
Real World Haskell Chapter 8 Solutions
AlternativeBit — 3/28/2017
Hello, it’s been a long time. Despite having done some progress on the resolution of the exercises of this book, I haven’t blogged about my solutions, which is a shame. The solutions are available in this git repository though. Let’s start again…
Bayesian Ranking for Rated Items
Math ∩ Programming — 3/13/2017
Problem: You have a catalog of items with discrete ratings (thumbs up/thumbs down, or 5-star ratings, etc.), and you want to display them in the “right” order. Solution: In Python ‘’’ score: [int], [int], [float] -> float Return the expected value…
The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm
Math ∩ Programming — 2/27/2017
papad Hard to believe Sanjeev Arora and his coauthors consider it “a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” Christos Papadimitriou calls it “so hard…
Real World Haskell Chapter 4 Solutions
AlternativeBit — 12/18/2016
Okay, in this chapter, we will apparently learn more about common techniques in FP, can’t wait! Exercises page 84 Let’s rewrite safe versions of partial list functions The first two functions are very straightforward: a bit of pattern…
A Spectral Analysis of Moore Graphs
Math ∩ Programming — 11/3/2016
For fixed integers $ r > 0$, and odd $ g$, a Moore graph is an $ r$-regular graph of girth $ g$ which has the minimum number of vertices $ n$ among all such graphs with the same regularity and girth. (Recall, A the girth of a graph is the length of…
Voltage, Temperature, and Harmonic Functions
Math ∩ Programming — 9/26/2016
This is a guest post by my friend and colleague Samantha Davies. Samantha is a math Ph.D student at the University of Washington, and a newly minted math blogger. Go check out her blog, With High Probability. If I said “let’s talk about temperature…
Guest post, “What’s up with graph Laplacians?”
Math ∩ Programming — 9/20/2016
I wrote a guest post for my friend Samantha Davies’s blog, With High Probability. It’s called, What’s up with graph Laplacians? Go check it out!
Zero-Knowledge: Definitions and Theory
Math ∩ Programming — 9/19/2016
The next Monday, when the fathers were all back at work, we kids were playing in a field. One kid says to me, “See that bird? What kind of bird is that?” I said, “I haven’t the slightest idea what kind of a bird it is.” He says, “It’s a…
Zero Knowledge Proofs for NP
Math ∩ Programming — 8/1/2016
Last time, we saw a specific zero-knowledge proof for graph isomorphism. This introduced us to the concept of an interactive proof, where you have a prover and a verifier sending messages back and forth, and the prover is trying to prove a specific…
The Blum-Blum-Shub Pseudorandom Generator
Math ∩ Programming — 7/11/2016
Problem: Design a random number generator that is computationally indistinguishable from a truly random number generator. Solution (in Python): note this solution uses the Miller-Rabin primality tester, though any primality test will do. See the…
Open recipe database: how to gather, cure and store data
AlternativeBit — 7/8/2016
I recently started to think about creating an open recipe database. The major consideration coming with this project is how to gather, cure and store recipes. Gathering data Let’s start with something obvious: we cannot rely on users to create…
Zero Knowledge Proofs — A Primer
Math ∩ Programming — 7/5/2016
In this post we’ll get a strong taste for zero knowledge proofs by exploring the graph isomorphism problem in detail. In the next post, we’ll see how this relates to cryptography and the bigger picture. The goal of this post is to get a strong…
Some thoughts about building an open recipe database
AlternativeBit — 6/23/2016
Lately, I have been thinking about creating an open recipe database. It is just not possible to find any good quality recipes database. Often, the website indexing recipes does not expose its data using any kind of API. When it does - and very few…
Singular Value Decomposition Part 2: Theorem, Proof, Algorithm
Math ∩ Programming — 5/16/2016
I’m just going to jump right into the definitions and rigor, so if you haven’t read the previous post motivating the singular value decomposition, go back and do that first. This post will be theorem, proof, algorithm, data. The data set we test on…
Singular Value Decomposition Part 1: Perspectives on Linear Algebra
Math ∩ Programming — 4/18/2016
The singular value decomposition (SVD) of a matrix is a fundamental tool in computer science, data analysis, and statistics. It’s used for all kinds of applications from regression to prediction, to finding approximate solutions to optimization…
Tensorphobia and the Outer Product
Math ∩ Programming — 3/28/2016
Variations on a theme Back in 2014 I wrote a post called How to Conquer Tensorphobia that should end up on Math $ \cap$ Programming’s “greatest hits” album. One aspect of tensors I neglected to discuss was the connection between the modern views of…
My Graduate Career in Math
Math ∩ Programming — 3/5/2016
2010–2011 (Year 0) I had just switched my major at Cal Poly State University from computer science to math. I wanted to double major but California was in a budget crisis and a few weeks before I tried submitting my double-major request the Provost…
Big Dimensions, and What You Can Do About It
Math ∩ Programming — 2/8/2016
Data is abundant, data is big, and big is a problem. Let me start with an example. Let’s say you have a list of movie titles and you want to learn their genre: romance, action, drama, etc. And maybe in this scenario IMDB doesn’t exist so you can’t…
Concrete Examples of Quantum Gates
Math ∩ Programming — 1/11/2016
So far in this series we’ve seen a lot of motivation and defined basic ideas of what a quantum circuit is. But on rereading my posts, I think we would all benefit from some concreteness. “Local” operations So by now we’ve understood that quantum…
Hashing to Estimate the Size of a Stream
Math ∩ Programming — 1/4/2016
Problem: Estimate the number of distinct items in a data stream that is too large to fit in memory. Solution: (in python) import random def randomHash(modulus): a, b = random.randint(0,modulus-1), random.randint(0,modulus-1) def f(x): return (a*x +…
Load Balancing and the Power of Hashing
Math ∩ Programming — 12/28/2015
Here’s a bit of folklore I often hear (and retell) that’s somewhere between a joke and deep wisdom: if you’re doing a software interview that involves some algorithms problem that seems hard, your best bet is to use hash tables. More succinctly…
How to configure TLS Let’s Encrypt Certificates with Nginx
AlternativeBit — 12/4/2015
Let’s encrypt beta is public since yesterday. I already use their certificates for several domains. The main problem I actually face is certificates renewal. I want to be able to renew automatically my certificates without turning off Nginx. Let’s…
The Inequality
Math ∩ Programming — 11/24/2015
Math and computer science are full of inequalities, but there is one that shows up more often in my work than any other. Of course, I’m talking about \(\displaystyle 1+x \leq e^{x}\) This is The Inequality. I’ve been told on many occasions that the…
A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details
Math ∩ Programming — 11/12/2015
Update 2017-01-09: Laci claims to have found a workaround to the previously posted error, and the claim is again quasipolynoimal time! Updated arXiv paper to follow. Update 2017-01-04: Laci has posted an update on his paper. The short version is…
Serial Dictatorships and House Allocation
Math ∩ Programming — 10/26/2015
I was recently an invited speaker in a series of STEM talks at Moraine Valley Community College. My talk was called “What can algorithms tell us about life, love, and happiness?” and it’s on Youtube now so you can go watch it. The central theme of…
One definition of algorithmic fairness: statistical parity
Math ∩ Programming — 10/19/2015
If you haven’t read the first post on fairness, I suggest you go back and read it because it motivates why we’re talking about fairness for algorithms in the first place. In this post I’ll describe one of the existing mathematical definitions of…
The Boosting Margin, or Why Boosting Doesn’t Overfit
Math ∩ Programming — 9/21/2015
There’s a well-understood phenomenon in machine learning called overfitting. The idea is best shown by a graph: overfitting Let me explain. The vertical axis represents the error of a hypothesis. The horizontal axis represents the complexity of the…
The Welch-Berlekamp Algorithm for Correcting Errors in Data
Math ∩ Programming — 9/7/2015
In this post we’ll implement Reed-Solomon error-correcting codes and use them to play with codes. In our last post we defined Reed-Solomon codes rigorously, but in this post we’ll focus on intuition and code. As usual the code and data used in this…
The Čech Complex and the Vietoris-Rips Complex
Math ∩ Programming — 8/6/2015
It’s about time we got back to computational topology. Previously in this series we endured a lightning tour of the fundamental group and homology, then we saw how to compute the homology of a simplicial complex using linear algebra. What we really…
What does it mean for an algorithm to be fair?
Math ∩ Programming — 7/13/2015
In 2014 the White House commissioned a 90-day study that culminated in a report (pdf) on the state of “big data” and related technologies. The authors give many recommendations, including this central warning. Warning: algorithms can facilitate…
Methods of Proof — Diagonalization
Math ∩ Programming — 6/8/2015
A while back we featured a post about why learning mathematics can be hard for programmers, and I claimed a major issue was not understanding the basic methods of proof (the lingua franca between intuition and rigorous mathematics). I boiled these…
Weak Learning, Boosting, and the AdaBoost algorithm
Math ∩ Programming — 5/18/2015
When addressing the question of what it means for an algorithm to learn, one can imagine many different models, and there are quite a few. This invariably raises the question of which models are “the same” and which are “different,” along with a…
The Many Faces of Set Cover
Math ∩ Programming — 5/4/2015
A while back Peter Norvig posted a wonderful pair of articles about regex golf. The idea behind regex golf is to come up with the shortest possible regular expression that matches one given list of strings, but not the other. “Regex Golf,” by…
Markov Chain Monte Carlo Without all the Bullshit
Math ∩ Programming — 4/6/2015
I have a little secret: I don’t like the terminology, notation, and style of writing in statistics. I find it unnecessarily complicated. This shows up when trying to read about Markov Chain Monte Carlo methods. Take, for example, the abstract to…
The Codes of Solomon, Reed, and Muller
Math ∩ Programming — 3/23/2015
Last time we defined the Hamming code. We also saw that it meets the Hamming bound, which is a measure of how densely a code can be packed inside an ambient space and still maintain a given distance. This time we’ll define the Reed-Solomon code…
Finding the majority element of a stream
Math ∩ Programming — 3/9/2015
Problem: Given a massive data stream of $ n$ values in $ { 1, 2, \dots, m }$ and the guarantee that one value occurs more than $ n/2$ times in the stream, determine exactly which value does so. Solution: (in Python) def majority(stream): held =…
Hamming’s Code
Math ∩ Programming — 3/2/2015
Or how to detect and correct errors Last time we made a quick tour through the main theorems of Claude Shannon, which essentially solved the following two problems about communicating over a digital channel. What is the best encoding for…
A Proofless Introduction to Information Theory
Math ∩ Programming — 2/16/2015
There are two basic problems in information theory that are very easy to explain. Two people, Alice and Bob, want to communicate over a digital channel over some long period of time, and they know the probability that certain messages will be sent…
Zero-One Laws for Random Graphs
Math ∩ Programming — 2/9/2015
Last time we saw a number of properties of graphs, such as connectivity, where the probability that an Erdős–Rényi random graph $ G(n,p)$ satisfies the property is asymptotically either zero or one. And this zero or one depends on whether the…
The Giant Component and Explosive Percolation
Math ∩ Programming — 2/2/2015
Last time we left off with a tantalizing conjecture: a random graph with edge probability $ p = 5/n$ is almost surely a connected graph. We arrived at that conjecture from some ad-hoc data analysis, so let’s go back and treat it with some more…
Multiple Qubits and the Quantum Circuit
Math ∩ Programming — 1/26/2015
Last time we left off with the tantalizing question: how do you do a quantum “AND” operation on two qubits? In this post we’ll see why the tensor product is the natural mathematical way to represent the joint state of multiple qubits. Then we’ll…
The Quantum Bit
Math ∩ Programming — 12/15/2014
The best place to start our journey through quantum computing is to recall how classical computing works and try to extend it. Since our final quantum computing model will be a circuit model, we should informally discuss circuits first. A circuit…
A Motivation for Quantum Computing
Math ∩ Programming — 12/8/2014
Quantum mechanics is one of the leading scientific theories describing the rules that govern the universe. It’s discovery and formulation was one of the most important revolutions in the history of mankind, contributing in no small part to the…
Linear Programming and the Simplex Algorithm
Math ∩ Programming — 12/1/2014
In the last post in this series we saw some simple examples of linear programs, derived the concept of a dual linear program, and saw the duality theorem and the complementary slackness conditions which give a rough sketch of the stopping criterion…
Learning a single-variable polynomial, or the power of adaptive queries
Math ∩ Programming — 11/18/2014
Problem: Alice chooses a secret polynomial $ p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $ p(x)$ for some integer $ x$ of Bob’s choice. What is the minimal number of queries…
The Complexity of Communication
Math ∩ Programming — 11/10/2014
satellite One of the most interesting questions posed in the last thirty years of computer science is to ask how much “information” must be communicated between two parties in order for them to jointly compute something. One can imagine these two…
On the Computational Complexity of MapReduce
Math ∩ Programming — 10/5/2014
I recently wrapped up a fun paper with my coauthors Ben Fish, Adam Lelkes, Lev Reyzin, and Gyorgy Turan in which we analyzed the computational complexity of a model of the popular MapReduce framework. Check out the preprint on the arXiv. Update:…
Making Hybrid Images
Math ∩ Programming — 9/29/2014
The Mona Lisa Leonardo da Vinci’s Mona Lisa is one of the most famous paintings of all time. And there has always been a discussion around her enigmatic smile. He used a trademark Renaissance technique called sfumato, which involves many thin…
Occam’s Razor and PAC-learning
Math ∩ Programming — 9/19/2014
So far our discussion of learning theory has been seeing the definition of PAC-learning, tinkering with it, and seeing simple examples of learnable concept classes. We’ve said that our real interest is in proving big theorems about what big classes…
A Rook Game
Math ∩ Programming — 8/31/2014
Problem: Two players take turns moving a rook on an 8×8 chessboard. The rook is only allowed to move south or west (but not both in a single turn), and may move any number of squares in the chosen direction on a turn. The loser is the player who…
When Greedy Algorithms are Perfect: the Matroid
Math ∩ Programming — 8/26/2014
Greedy algorithms are by far one of the easiest and most well-understood algorithmic techniques. There is a wealth of variations, but at its core the greedy algorithm optimizes something using the natural rule, “pick what looks best” at any step….
Parameterizing the Vertex Cover Problem
Math ∩ Programming — 8/25/2014
I’m presenting a paper later this week at the Matheamtical Foundations of Computer Science 2014 in Budapest, Hungary. This conference is an interesting mix of logic and algorithms that aims to bring together researchers from these areas to discuss…
An Update on “Coloring Resilient Graphs”
Math ∩ Programming — 7/14/2014
A while back I announced a preprint of a paper on coloring graphs with certain resilience properties. I’m pleased to announce that it’s been accepted to the Mathematical Foundations of Computer Science 2014, which is being held in Budapest this…
When Greedy Algorithms are Good Enough: Submodularity and the (1—1/e)-Approximation
Math ∩ Programming — 7/7/2014
Greedy algorithms are among the simplest and most intuitive algorithms known to humans. Their name essentially gives their description: do the thing that looks best right now, and repeat until nothing looks good anymore or you’re forced to stop….
The Mathematics of Secret Sharing
Math ∩ Programming — 6/23/2014
Here’s a simple puzzle with a neat story. A rich old woman is drafting her will and wants to distribute her expansive estate equally amongst her five children. But her children are very greedy, and the woman knows that if he leaves her will…
Linear Programming and Healthy Diets — Part 1
Math ∩ Programming — 6/2/2014
Optimization is by far one of the richest ways to apply computer science and mathematics to the real world. Everybody is looking to optimize something: companies want to maximize profits, factories want to maximize efficiency, investors want to…
Learning to Love Complex Numbers
Math ∩ Programming — 5/26/2014
This post is intended for people with a little bit of programming experience and no prior mathematical background. So let’s talk about numbers. Numbers are curious things. On one hand, they represent one of the most natural things known to humans,…
Community Detection in Graphs — a Casual Tour
Math ∩ Programming — 5/19/2014
Graphs are among the most interesting and useful objects in mathematics. Any situation or idea that can be described by objects with connections is a graph, and one of the most prominent examples of a real-world graph that one can come up with is a…
A problem that is not (properly) PAC-learnable
Math ∩ Programming — 4/21/2014
In a previous post we introduced a learning model called Probably Approximately Correct (PAC). We saw an example of a concept class that was easy to learn: intervals on the real line (and more generally, if you did the exercise, axis-aligned…
Sending and Authenticating Messages with Elliptic Curves
Math ∩ Programming — 4/14/2014
Last time we saw the Diffie-Hellman key exchange protocol, and discussed the discrete logarithm problem and the related Diffie-Hellman problem, which form the foundation for the security of most protocols that use elliptic curves. Let’s continue…
Stable Marriages and Designing Markets
Math ∩ Programming — 4/2/2014
Here is a fun puzzle. Suppose we have a group of 10 men and 10 women, and each of the men has sorted the women in order of their preference for marriage (that is, a man prefers to marry a woman earlier in his list over a woman later in the list)….
Elliptic Curve Diffie-Hellman
Math ∩ Programming — 3/31/2014
So far in this series we’ve seen elliptic curves from many perspectives, including the elementary, algebraic, and programmatic ones. We implemented finite field arithmetic and connected it to our elliptic curve code. So we’re in a perfect position…
Connecting Elliptic Curves with Finite Fields
Math ∩ Programming — 3/19/2014
So here we are. We’ve studied the general properties of elliptic curves, written a program for elliptic curve arithmetic over the rational numbers, and taken a long detour to get some familiarity with finite fields (the mathematical background and…
Want to make a great puzzle game? Get inspired by theoretical computer science.
Math ∩ Programming — 3/17/2014
Two years ago, Erik Demaine and three other researchers published a fun paper to the arXiv proving that most incarnations of classic nintendo games are NP-hard. This includes almost every Super Mario Brothers, Donkey Kong, and Pokemon title. Back…
Programming with Finite Fields
Math ∩ Programming — 3/13/2014
Back when I was first exposed to programming language design, I decided it would be really cool if there were a language that let you define your own number types and then do all your programming within those number types. And since I get excited…
Martingales and the Optional Stopping Theorem
Math ∩ Programming — 3/3/2014
This is a guest post by my colleague Adam Lelkes. The goal of this primer is to introduce an important and beautiful tool from probability theory, a model of fair betting games called martingales. In this post I will assume that the reader is…
(Finite) Fields — A Primer
Math ∩ Programming — 2/26/2014
So far on this blog we’ve given some introductory notes on a few kinds of algebraic structures in mathematics (most notably groups and rings, but also monoids). Fields are the next natural step in the progression. If the reader is comfortable with…
Elliptic Curves as Python Objects
Math ∩ Programming — 2/24/2014
Last time we saw a geometric version of the algorithm to add points on elliptic curves. We went quite deep into the formal setting for it (projective space $ \mathbb{P}^2$), and we spent a lot of time talking about the right way to define the…
On Coloring Resilient Graphs
Math ∩ Programming — 2/21/2014
I’m pleased to announce that another paper of mine is finished. This one just got accepted to MFCS 2014, which is being held in Budapest this year (this whole research thing is exciting!). This is joint work with my advisor, Lev Reyzin. As with my…
Elliptic Curves as Algebraic Structures
Math ∩ Programming — 2/16/2014
Last time we looked at the elementary formulation of an elliptic curve as the solutions to the equation \(y^2 = x^3 + ax + b\) where $ a,b$ are such that the discriminant is nonzero: \(-16(4a^3 + 27b^2) \neq 0\) We have yet to explain why we want…
Simulating a Biased Coin with a Fair Coin
Math ∩ Programming — 2/12/2014
This is a guest post by my friend and colleague Adam Lelkes. Adam’s interests are in algebra and theoretical computer science. This gem came up because Adam gave a talk on probabilistic computation in which he discussed this technique. Problem:…
Elliptic Curves as Elementary Equations
Math ∩ Programming — 2/10/2014
Finding solutions to systems of polynomial equations is one of the oldest and deepest problems in all of mathematics. This is broadly the domain of algebraic geometry, and mathematicians wield some of the most sophisticated and abstract tools…
Simulating a Fair Coin with a Biased Coin
Math ∩ Programming — 2/8/2014
This is a guest post by my friend and colleague Adam Lelkes. Adam’s interests are in algebra and theoretical computer science. This gem came up because Adam gave a talk on probabilistic computation in which he discussed this technique. Problem:…
Introducing Elliptic Curves
Math ∩ Programming — 2/8/2014
With all the recent revelations of government spying and backdoors into cryptographic standards, I am starting to disagree with the argument that you should never roll your own cryptography. Of course there are massive pitfalls and very few people…
Fixing Bugs in “Computing Homology”
Math ∩ Programming — 1/24/2014
A few awesome readers have posted comments in Computing Homology to the effect of, “Your code is not quite correct!” And they’re right! Despite the almost year since that post’s publication, I haven’t bothered to test it for more complicated…
RealityMining, a Case Study in the Woes of Data Processing
Math ∩ Programming — 1/22/2014
This post is intended to be a tutorial on how to access the RealityMining dataset using Python (because who likes Matlab?), and a rant on how annoying the process was to figure out. RealityMining is a dataset of smart-phone data logs from a group…
How to Conquer Tensorphobia
Math ∩ Programming — 1/17/2014
A professor at Stanford once said, If you really want to impress your friends and confound your enemies, you can invoke tensor products… People run in terror from the $ \otimes$ symbol. He was explaining some aspects of multidimensional Fourier…
Probably Approximately Correct — a Formal Theory of Learning
Math ∩ Programming — 1/2/2014
In tackling machine learning (and computer science in general) we face some deep philosophical questions. Questions like, “What does it mean to learn?” and, “Can a computer learn?” and, “How do you define simplicity?” and, “Why does Occam’s Razor…
The Two-Dimensional Fourier Transform and Digital Watermarking
Math ∩ Programming — 12/30/2013
We’ve studied the Fourier transform quite a bit on this blog: with four primers and the Fast Fourier Transform algorithm under our belt, it’s about time we opened up our eyes to higher dimensions. Indeed, in the decades since Cooley & Tukey’s…
Bandits and Stocks
Math ∩ Programming — 12/9/2013
So far in this series we’ve seen two nontrivial algorithms for bandit learning in two different settings. The first was the UCB1 algorithm, which operated under the assumption that the rewards for the trials were independent and stochastic. That…
Lagrangians for the Amnesiac
Math ∩ Programming — 11/30/2013
For a while I’ve been meaning to do some more advanced posts on optimization problems of all flavors. One technique that comes up over and over again is Lagrange multipliers, so this post is going to be a leisurely reminder of that technique. I…
Adversarial Bandits and the Exp3 Algorithm
Math ∩ Programming — 11/8/2013
In the last twenty years there has been a lot of research in a subfield of machine learning called Bandit Learning. The name comes from the problem of being faced with a large sequence of slot machines (once called one-armed bandits) each with a…
Optimism in the Face of Uncertainty: the UCB1 Algorithm
Math ∩ Programming — 10/28/2013
startups The software world is always atwitter with predictions on the next big piece of technology. And a lot of chatter focuses on what venture capitalists express interest in. As an investor, how do you pick a good company to invest in? Do you…
The Universal Properties of Map, Fold, and Filter
Math ∩ Programming — 9/30/2013
A lot of people who like functional programming often give the reason that the functional style is simply more elegant than the imperative style. When compelled or inspired to explain (as I did in my old post, How I Learned to Love Functional…
Anti-Coordination Games and Stable Graph Colorings
Math ∩ Programming — 9/9/2013
My First Paper I’m pleased to announce that my first paper, titled “Anti-Coordination Games and Stable Colorings,” has been accepted for publication! The venue is the Symposium on Algorithmic Game Theory, which will take place in Aachen, Germany…
The Erdős-Rényi Random Graph
Math ∩ Programming — 8/22/2013
During the 1950’s the famous mathematician Paul Erdős and Alfred Rényi put forth the concept of a random graph and in the subsequent years of study transformed the world of combinatorics. The random graph is the perfect example of a good…
Linear Regression
Math ∩ Programming — 8/18/2013
Machine learning is broadly split into two camps, statistical learning and non-statistical learning. The latter we’ve started to get a good picture of on this blog; we approached Perceptrons, decision trees, and neural networks from a…
Cauchy-Schwarz Inequality (and Amplification)
Math ∩ Programming — 7/23/2013
| Problem: Prove that for vectors $ v, w$ in an inner product space, the inequality $$\displaystyle | \left \langle v, w \right \rangle | \leq | v | | w |$$ Solution: There is an elementary proof of the Cauchy-Schwarz inequality (see the Wikipedia… |
Functoriality
Math ∩ Programming — 7/14/2013
Last time we worked through some basic examples of universal properties, specifically singling out quotients, products, and coproducts. There are many many more universal properties that we will mention as we encounter them, but there is one…
Reservoir Sampling
Math ∩ Programming — 7/5/2013
Problem: Given a data stream of unknown size $ n$, pick an entry uniformly at random. That is, each entry has a $ 1/n$ chance of being chosen. Solution: (in Python) import random def reservoirSample(stream): for k,x in enumerate(stream, start=1):…
Guest Post: Torus-Knotted Baklava
Math ∩ Programming — 6/28/2013
Guest Post: Torus-Knotted Baklava at Baking And Math, a blog by my friend and colleague, Yen.
Miller-Rabin Primality Test
Math ∩ Programming — 6/16/2013
Problem: Determine if a number is prime, with an acceptably small error rate. Solution: (in Python) import random def decompose(n): exponentOfTwo = 0 while n % 2 == 0: n = n/2 exponentOfTwo += 1 return exponentOfTwo, n def…
Why Theoretical Computer Scientists Aren’t Worried About Privacy
Math ∩ Programming — 6/10/2013
There has been a lot of news recently on government surveillance of its citizens. The biggest two that have pervaded my news feeds are the protests in Turkey, which in particular have resulted in particular oppression of social media users, and the…
Conferences, Summer Work, and an Advisor
Math ∩ Programming — 6/3/2013
I’ve been spending a little less time on my blog recently then I’d like to, but for good reason: I’ve been attending two weeks of research conferences, I’m getting ready for a summer internship in cybersecurity, and I’ve finally chosen an…
Rings — A Second Primer
Math ∩ Programming — 6/2/2013
Last time we defined and gave some examples of rings. Recapping, a ring is a special kind of group with an additional multiplication operation that “plays nicely” with addition. The important thing to remember is that a ring is intended to remind…
Universal Properties
Math ∩ Programming — 5/24/2013
Previously in this series we’ve seen the definition of a category and a bunch of examples, basic properties of morphisms, and a first look at how to represent categories as types in ML. In this post we’ll expand these ideas and introduce the notion…
Properties of Morphisms
Math ∩ Programming — 5/15/2013
This post is mainly mathematical. We left it out of our introduction to categories for brevity, but we should lay these definitions down and some examples before continuing on to universal properties and doing more computation. The reader should…
Bezier Curves and Picasso
Math ∩ Programming — 5/11/2013
Pablo Picasso Simplicity and the Artist Some of my favorite of Pablo Picasso’s works are his line drawings. He did a number of them about animals: an owl, a camel, a butterfly, etc. This piece called “Dog” is on my wall: Dachshund-Picasso-Sketch…
Categories as Types
Math ∩ Programming — 5/4/2013
In this post we’ll get a quick look at two ways to define a category as a type in ML. The first way will be completely trivial: we’ll just write it as a tuple of functions. The second will involve the terribly-named “functor” expression in ML,…
Rings — A Primer
Math ∩ Programming — 4/30/2013
Previously on this blog, we’ve covered two major kinds of algebraic objects: the vector space and the group. There are at least two more fundamental algebraic objects every mathematician should something know about. The first, and the focus of this…
Introducing Categories
Math ∩ Programming — 4/24/2013
For a list of all the posts on Category Theory, see the Main Content page. It is time for us to formally define what a category is, to see a wealth of examples. In our next post we’ll see how the definitions laid out here translate to programming…
Categories, What’s the Point?
Math ∩ Programming — 4/16/2013
Perhaps primarily due to the prominence of monads in the Haskell programming language, programmers are often curious about category theory. Proponents of Haskell and other functional languages can put category-theoretic concepts on a pedestal or in…
Probabilistic Bounds — A Primer
Math ∩ Programming — 4/15/2013
Probabilistic arguments are a key tool for the analysis of algorithms in machine learning theory and probability theory. They also assume a prominent role in the analysis of randomized and streaming algorithms, where one imposes a restriction on…
Computing Homology
Math ∩ Programming — 4/10/2013
Update: the mistakes made in the code posted here are fixed and explained in a subsequent post (one minor code bug was fixed here, and a less minor conceptual bug is fixed in the linked post). In our last post in this series on topology, we defined…
A Sample of Standard ML, the TreeSort Algorithm, and Monoids
Math ∩ Programming — 4/8/2013
In this post we will assume the reader has a passing familiarity with some of the basic concepts of functional programming (the map, fold, and filter functions). We introduce these topics in our Racket primer, but the average reader will understand…
Homology Theory — A Primer
Math ∩ Programming — 4/3/2013
This series on topology has been long and hard, but we’re are quickly approaching the topics where we can actually write programs. For this and the next post on homology, the most important background we will need is a solid foundation in linear…
Conditional (Partitioned) Probability — A Primer
Math ∩ Programming — 3/28/2013
One of the main areas of difficulty in elementary probability, and one that requires the highest levels of scrutiny and rigor, is conditional probability. The ideas are simple enough: that we assign probabilities relative to the occurrence of some…
Methods of Proof — Induction
Math ∩ Programming — 3/21/2013
In this final post on the basic four methods of proof (but perhaps not our last post on proof methods), we consider the proof by induction. Proving Statements About All Natural Numbers Induction comes in many flavors, but the goal never changes. We…
Seam Carving for Content-Aware Image Scaling
Math ∩ Programming — 3/5/2013
The Problem with Cropping Every programmer or graphic designer with some web development experience can attest to the fact that finding good images that have an exactly specified size is a pain. Since the dimensions of the sought picture are…
Methods of Proof — Contradiction
Math ∩ Programming — 2/28/2013
In this post we’ll expand our toolbox of proof techniques by adding the proof by contradiction. We’ll also expand on our knowledge of functions on sets, and tackle our first nontrivial theorem: that there is more than one kind of…
Methods of Proof — Contrapositive
Math ∩ Programming — 2/22/2013
In this post we’ll cover the second of the “basic four” methods of proof: the contrapositive implication. We will build off our material from last time and start by defining functions on sets. Functions as Sets So far we have become comfortable…
Methods of Proof — Direct Implication
Math ∩ Programming — 2/16/2013
I recently posted an exploratory piece on why programmers who are genuinely interested in improving their mathematical skills can quickly lose stamina or be deterred. My argument was essentially that they don’t focus enough on mastering the basic…
Why there is no Hitchhiker’s Guide to Mathematics for Programmers
Math ∩ Programming — 2/8/2013
For those who aren’t regular readers: as a followup to this post, there are four posts detailing the basic four methods of proof, with intentions to detail some more advanced proof techniques in the future. You can find them on this blog’s primers…
k-Means Clustering and Birth Rates
Math ∩ Programming — 2/4/2013
A common problem in machine learning is to take some kind of data and break it up into “clumps” that best reflect how the data is structured. A set of points which are all collectively close to each other should be in the same clump. A simple…
Depth- and Breadth-First Search
Math ∩ Programming — 1/22/2013
The graph is among the most common data structures in computer science, and it’s unsurprising that a staggeringly large amount of time has been dedicated to developing algorithms on graphs. Indeed, many problems in areas ranging from sociology,…
The Fundamental Group — A Primer
Math ∩ Programming — 1/12/2013
Being part of the subject of algebraic topology, this post assumes the reader has read our previous primers on both topology and group theory. As a warning to the reader, it is more advanced than most of the math presented on this blog, and it is…
Probability Theory — A Primer
Math ∩ Programming — 1/4/2013
It is a wonder that we have yet to officially write about probability theory on this blog. Probability theory underlies a huge portion of artificial intelligence, machine learning, and statistics, and a number of our future posts will rely on the…
Groups — A Second Primer
Math ∩ Programming — 12/22/2012
The First Isomorphism Theorem The meat of our last primer was a proof that quotient groups are well-defined. One important result that helps us compute groups is a very easy consequence of this well-definition. Recall that if $ G,H$ are groups and…
Neural Networks and the Backpropagation Algorithm
Math ∩ Programming — 12/9/2012
Neurons, as an Extension of the Perceptron Model In a previous post in this series we investigated the Perceptron model for determining whether some data was linearly separable. That is, given a data set where the points are labelled in one of two…
Groups — A Primer
Math ∩ Programming — 12/9/2012
The study of groups is often one’s first foray into advanced mathematics. In the naivete of set theory one develops tools for describing basic objects, and through a first run at analysis one develops a certain dexterity for manipulating symbols…
Information Distance — A Primer
Math ∩ Programming — 12/4/2012
This post assumes familiarity with our primer on Kolmogorov complexity. We recommend the uninformed reader begin there. We will do our best to keep consistent notation across both posts. Kolmogorov Complexity as a Metric Over the past fifty years…
Ramsey Number Lower Bound
Math ∩ Programming — 12/2/2012
Define the Ramsey number $ R(k,m)$ to be the minimum number $ n$ of vertices required of the complete graph $ K_n$ so that for any two-coloring (red, blue) of the edges of $ K_n$ one of two things will happen: There is a red $ k$-clique; that is, a…
Constructing Topological Spaces — A Primer
Math ∩ Programming — 11/11/2012
Last time we investigated the (very unintuitive) concept of a topological space as a set of “points” endowed with a description of which subsets are open. Now in order to actually arrive at a discussion of interesting and useful topological spaces,…
There are Infinitely Many Primes (Erdős)
Math ∩ Programming — 11/10/2012
Problem: Prove there are infinitely many primes Solution: Denote by $ \pi(n)$ the number of primes less than or equal to $ n$. We will give a lower bound on $ \pi(n)$ which increases without bound as $ n \to \infty$. Note that every number $ n$ can…
Topological Spaces — A Primer
Math ∩ Programming — 11/5/2012
In our last primer we looked at a number of interesting examples of metric spaces, that is, spaces in which we can compute distance in a reasonable way. Our goal for this post is to relax this assumption. That is, we want to study the geometric…
Decision Trees and Political Party Classification
Math ∩ Programming — 10/8/2012
Last time we investigated the k-nearest-neighbors algorithm and the underlying idea that one can learn a classification rule by copying the known classification of nearby data points. This required that we view our data as sitting inside a metric…
Complete Sequences and Magic Tricks
Math ∩ Programming — 10/2/2012
Numberphile posted a video today describing a neat trick based on complete sequences: The mathematics here is pretty simple, but I noticed at the end of the video that Dr. Grime was constructing the cards by hand, when really this is a job for a…
Infinitely Many Primes (Using Topology)
Math ∩ Programming — 9/26/2012
Problem: Prove there are infinitely many prime numbers. Solution: First recall that an arithmetic progression with difference $ d$ is a sequence of integers $ a_n \subset \mathbb{Z}$ so that for every pair $ a_k, a_{k+1}$ the difference $ a_{k+1} –…
Trees—A Primer
Math ∩ Programming — 9/17/2012
This post comes in preparation for a post on decision trees (a specific type of tree used for classification in machine learning). While most mathematicians and programmers are familiar with trees, we have yet to discuss them on this blog. For…
K-Nearest-Neighbors and Handwritten Digit Classification
Math ∩ Programming — 8/26/2012
The Recipe for Classification One important task in machine learning is to classify data into one of a fixed number of classes. For instance, one might want to discriminate between useful email and unsolicited spam. Or one might wish to determine…
Metric Spaces — A Primer
Math ∩ Programming — 8/26/2012
The Blessing of Distance We have often mentioned the idea of a “metric” on this blog, and we briefly described a formal definition for it. Colloquially, a metric is simply the mathematical notion of a distance function, with certain well-behaved…
Machine Learning — Introduction
Math ∩ Programming — 8/4/2012
A Series on Machine Learning These days an absolutely staggering amount of research and development work goes into the very coarsely defined field of “machine learning.” Part of the reason why it’s so coarsely defined is because it borrows…
The Cellular Automaton Method for Cave Generation
Math ∩ Programming — 7/29/2012
Dear reader, this post has an interactive simulation! We encourage you to play with it as you read the article below. In our series of posts on cellular automata, we explored Conway’s classic Game of Life and discovered some interesting patterns…
Dynamic Time Warping for Sequence Comparison
Math ∩ Programming — 7/25/2012
Problem: Write a program that compares two sequences of differing lengths for similarity. Solution: (In Python) import math def dynamicTimeWarp(seqA, seqB, d = lambda x,y: abs(x-y)): # create the cost matrix numRows, numCols = len(seqA), len(seqB)…
The Fast Fourier Transform
Math ∩ Programming — 7/18/2012
It’s often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey’s paper, “An Algorithm for the Machine Calculation of Complex Fourier Series.” They published a landmark algorithm which has since been…
Principal Component Analysis
Math ∩ Programming — 6/28/2012
Problem: Reduce the dimension of a data set, translating each data point into a representation that captures the “most important” features. Solution: in Python import numpy def principalComponents(matrix): # Columns of matrix correspond to data…
The Discrete Fourier Transform — A Primer
Math ∩ Programming — 6/23/2012
So here we are. We have finally made it to a place where we can transition with confidence from the classical continuous Fourier transform to the discrete version, which is the foundation for applications of Fourier analysis to programming. Indeed,…
Streaming Median
Math ∩ Programming — 6/15/2012
Problem: Compute a reasonable approximation to a “streaming median” of a potentially infinite sequence of integers. Solution: (in Python) def streamingMedian(seq): seq = iter(seq) m = 0 for nextElt in seq: if m > nextElt: m -= 1 elif m < nextElt: m…
Thoughts after a Year of Math ∩ Programming
Math ∩ Programming — 6/12/2012
After a year of writing this blog, what have I learned about the nature of the relationship between computer programs and mathematics? Here are a few notes that sum up my thoughts, roughly in order of how strongly I agree with them. I’d love to…
Generalized Functions — A Primer
Math ∩ Programming — 6/6/2012
Last time we investigated the naive (which I’ll henceforth call “classical”) notion of the Fourier transform and its inverse. While the development wasn’t quite rigorous, we nevertheless discovered elegant formulas and interesting properties that…
The Fourier Transform — A Primer
Math ∩ Programming — 5/27/2012
In our last primer we saw the Fourier series, which flushed out the notion that a periodic function can be represented as an infinite series of sines and cosines. While this is fine and dandy, and quite a powerful tool, it does not suffice for the…
Double Angle Trigonometric Formulas
Math ∩ Programming — 5/20/2012
Problem: Derive the double angle identities \(\sin(2\theta) = 2\sin(\theta)\cos(\theta)\\\ \cos(2\theta) = \cos^2(\theta) – \sin^2(\theta)\) Solution: Recall from linear algebra how one rotates a point in the plane. The matrix of rotation (derived…
False Proof – 2 = 4, As the Limit of an Infinite Power Tower
Math ∩ Programming — 5/5/2012
Problem: Prove that $ 2 = 4$. Solution: Consider the value of the following infinitely iterated exponent: \(\displaystyle \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}}\) Let $ a_n = \sqrt{2} \uparrow \uparrow n$, that is, the above power…
The Fourier Series—A Primer
Math ∩ Programming — 4/26/2012
Overview In this primer we’ll get a first taste of the mathematics that goes into the analysis of sound and images. In the next few primers, we’ll be building the foundation for a number of projects in this domain: extracting features of music for…
Kolmogorov Complexity—A Primer
Math ∩ Programming — 4/21/2012
The Complexity of Things Previously on this blog (quite a while ago), we’ve investigated some simple ideas of using randomness in artistic design (psychedelic art, and earlier randomized css designs). Here we intend to give a more thorough and…
Optimally Stacking the Deck—Texas Hold ‘Em
Math ∩ Programming — 4/9/2012
Main Theorem: There exist optimal stackings for standard two-player Texas Hold ‘Em. A Puzzle is Solved (and then some!) It’s been quite a while since we first formulated the idea of an optimal stacking. In the mean time, we’ve gotten distracted…
Classic Nintendo Games are NP-Hard
Math ∩ Programming — 3/22/2012
Problem: Prove that generalized versions of Mario Brothers, Metroid, Donkey Kong, Pokemon, and Legend of Zelda are NP-hard. Solution: http://arxiv.org/pdf/1203.1895v1.pdf Discussion: Three researchers (including Erik Demaine, a computer science…
Caching (and Memoization)
Math ∩ Programming — 3/22/2012
Problem: Remember results of a function call which requires a lot of computation. Solution: (in Python) def memoize(f): cache = {} def memoizedFunction(args): if args not in cache: cache[args] = f(args) return cache[args] memoizedFunction.cache =…
In Place Uniform Shuffle
Math ∩ Programming — 3/18/2012
Problem: Write a program that shuffles a list. Do so without using more than a constant amount of extra space and linear time in the size of the list. Solution: (in Python) import random random.seed() def shuffle(myList): n = len(myList) for i in…
Learning Programming — Finger-Painting and Killing Zombies
Math ∩ Programming — 3/15/2012
By the end, the breadth and depth of our collective knowledge was far beyond what anyone could expect from any high school course in any subject. Education Versus Exploration I’m a lab TA for an introductory Python programming course this semester,…
Other Complexity Classes
Math ∩ Programming — 2/29/2012
Not Just Time, But Space Too! So far on this blog we’ve introduced models for computation, focused on Turing machines and given a short overview of the two most fundamental classes of problems: P and NP. While the most significant open question in…
P vs. NP, A Primer (And a Proof Written in Racket)
Math ∩ Programming — 2/23/2012
Decidability Versus Efficiency In the early days of computing theory, the important questions were primarily about decidability. What sorts of problems are beyond the power of a Turing machine to solve? As we saw in our last primer on Turing…
Busy Beavers, and the Quest for Big Numbers
Math ∩ Programming — 2/8/2012
Finding Bigger Numbers, a Measure of Human Intellectual Progress Before we get into the nitty gritty mathematics, I’d like to mirror the philosophical and historical insights that one can draw from the study of large numbers. That may seem odd at…
Fundamental Theorem of Algebra (With Picard’s Little Theorem)
Math ∩ Programming — 2/7/2012
This post assumes familiarity with some basic concepts in complex analysis, including continuity and entire (everywhere complex-differentiable) functions. This is likely the simplest proof of the theorem (at least, among those that this author has…
Cryptanalysis with N-Grams
Math ∩ Programming — 2/3/2012
This post is the third post in a series on computing with natural language data sets. For the first two posts, see the relevant section of our main content page. A Childish Bit of Fun In this post, we focus on the problem of decoding substitution…
The Fundamental Theorem of Algebra (with Galois Theory)
Math ∩ Programming — 2/3/2012
This post assumes familiarity with some basic concepts in abstract algebra, specifically the terminology of field extensions, and the classical results in Galois theory and group theory. The fundamental theorem of algebra has quite a few number of…
Handshake Lemma
Math ∩ Programming — 1/30/2012
Problem: Prove or disprove: at a party of $ n$ people, there must be an even number of people who have an odd number of friends at the party. Solution: Let $ P$ be the set of all people, and for any person $ p \in P$, let $ d(p)$ be the number of…
The Fundamental Theorem of Algebra (with the Fundamental Group)
Math ∩ Programming — 1/22/2012
This post assumes familiarity with some basic concepts in algebraic topology, specifically what a group is and the definition of the fundamental group of a topological space. The fundamental theorem of algebra has quite a few number of proofs…
The Fundamental Theorem of Algebra (with Liouville)
Math ∩ Programming — 1/18/2012
This proof assumes knowledge of complex analysis, specifically the notions of analytic functions and Liouville’s Theorem (which we will state below). The fundamental theorem of algebra has quite a few number of proofs (enough to fill a book!). In…
Word Segmentation, or Makingsenseofthis
Math ∩ Programming — 1/15/2012
A First Look at Google’s N-Gram Corpus In this post we will focus on the problem of finding the appropriate word boundaries in strings like “homebuiltairplanes”, as is common in web URLs like www.homebuiltairplanes.com. This is an interesting…
A Spoonful of Python (and Dynamic Programming)
Math ∩ Programming — 1/13/2012
This primer is a third look at Python, and is admittedly selective in which features we investigate (for instance, we don’t use classes, as in our second primer on random psychedelic images). We do assume some familiarity with the syntax and basic…
Numerical Integration
Math ∩ Programming — 1/8/2012
Rectangles, Trapezoids, and Simpson’s I just wrapped up a semester of calculus TA duties, and I thought it would be fun to revisit the problem of integration from a numerical standpoint. In other words, the goal of this article is to figure out how…
Random (Psychedelic) Art
Math ∩ Programming — 1/1/2012
And a Pinch of Python Next semester I am a lab TA for an introductory programming course, and it’s taught in Python. My Python experience has a number of gaps in it, so we’ll have the opportunity for a few more Python primers, and small exercises…
Row Reduction Over A Field
Math ∩ Programming — 12/30/2011
We’re quite eager to get to applications of algebraic topology to things like machine learning (in particular, persistent homology). Even though there’s a massive amount of theory behind it (and we do plan to cover some of the theory), a lot of the…
Metrics on Words
Math ∩ Programming — 12/19/2011
We are about to begin a series where we analyze large corpora of English words. In particular, we will use a probabilistic analysis of Google’s ngrams to solve various tasks such as spelling correction, word segmentation, on-line typing prediction,…
Holidays and Homicide
Math ∩ Programming — 11/25/2011
A Study In Data Just before midnight on Thanksgiving, there was a murder by gunshot about four blocks from my home. Luckily I was in bed by then, but all of the commotion over the incident got me thinking: is murder disproportionately more common…
Tiling a Chessboard with Dominoes (Opposite Colors Removed)
Math ∩ Programming — 11/18/2011
This is a natural follow-up to our first gallery entry on the impossibility of tiling certain chessboards with dominoes. Problem: Suppose we remove two squares from a chessboard which have opposite color. Is it possible to tile the remaining…
Z[√2] has Infinitely Many Units
Math ∩ Programming — 11/7/2011
Note, while the problem below arose in ring theory (specifically, Euclidean domains), the proof itself is elementary, and so the title should not scare away any viewers. In fact, we boil the problem down to something which requires no knowledge of…
Conway’s Game of Life in Conway’s Game of Life
Math ∩ Programming — 11/3/2011
Recalling our series on Conway’s Game of Life, here is an implementation of Life within Life. Unfortunately, it does not “prove” what I hoped it might, so unless a reader has a suggestion on what this demonstration proves, it doesn’t belong in the…
False Proof: 1 = 2 (with Calculus)
Math ∩ Programming — 10/25/2011
Problem: Show 1 = 2 (with calculus) “Solution”: Consider the following: $ 1^2 = 1$ $ 2^2 = 2 + 2$ $ 3^2 = 3 + 3 + 3$ $ \vdots$ $ x^2 = x + x + \dots + x$ ($ x$ times) And since this is true for all values of $ x$, we may take the derivative of both…
The Smallest Non-Cyclic Simple Group has Order 60
Math ∩ Programming — 10/8/2011
Preamble: This proof is not particularly elegant or insightful. However, it belongs in this gallery for two reasons. First, it is an example of the goal of most mathematics: to classify things. In the same way that all natural numbers can be built…
A Taste of Racket
Math ∩ Programming — 10/3/2011
or, How I Learned to Love Functional Programming We recognize that not every reader has an appreciation for functional programming. Yet here on this blog, we’ve done most of our work in languages teeming with functional paradigms. It’s time for us…
N Choose 2 is the Sum of the First N-1 Integers
Math ∩ Programming — 10/2/2011
Problem: Determine an arithmetic expression for $ \binom{n}{2}$. Solution: The following picture describes a bijection between the set of yellow dots and the set of pairs of purple dots: In particular, selecting any yellow dots and travelling…
n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)
Math ∩ Programming — 9/5/2011
Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory. Problem: Let $ G$ be an infinite graph. Show that $ G$ is $ n$-colorable if and only if every finite subgraph $ G_0 \subset G$ is $…
Graduate Studies
Math ∩ Programming — 8/17/2011
I want to thank all my readers for visiting Math ∩ Programming as often as you do, and doubly thank those who are kind enough to leave a comment. UIC’s east side campus. My office building is unseen, to the left of this picture. Unfortunately over…
The Square Root of 2 is Irrational (Geometric Proof)
Math ∩ Programming — 8/14/2011
Problem: Show that $ \sqrt{2}$ is an irrational number (can’t be expressed as a fraction of integers). Solution: Suppose to the contrary that $ \sqrt{2} = a/b$ for integers $ a,b$, and that this representation is fully reduced, so that $…
The Perceptron, and All the Things it Can’t Perceive
Math ∩ Programming — 8/11/2011
This post assumes some basic familiarity with Euclidean geometry and linear algebra. Though we do not assume so much knowledge as is contained in our primer on inner product spaces, we will be working with the real Euclidean inner product. For the…
A Dash of Python
Math ∩ Programming — 8/10/2011
We will orient our dash of Python around the first and simplest problem from ProjectEuler.net. Installing Python To get Python on your computer, go to python’s website and follow the instructions for downloading and installing the interpreter. Most…
Programming Primers—An Introduction
Math ∩ Programming — 8/6/2011
So far on this blog we’ve assumed familiarity with the programming languages used (at the time of this writing, this is Mathematica and Java). This is unfair for the mathematicians who have little to no programming experience, and we admit that…
Number Theory—A Primer
Math ∩ Programming — 7/30/2011
This primer exists for the background necessary to read our post on RSA encryption, but it also serves as a general primer to number theory. Oh, Numbers, Numbers, Numbers We start with some easy definitions. Definition: The set of integers, denoted…
Encryption & RSA
Math ∩ Programming — 7/30/2011
This post assumes working knowledge of elementary number theory. Luckily for the non-mathematicians, we cover all required knowledge and notation in our number theory primer. So Three Thousand Years of Number Theory Wasn’t Pointless It’s often…
False Proof—All Numbers are Describable in at Most Twenty Words
Math ∩ Programming — 7/28/2011
Problem: Show that every natural number can be unambiguously described in fewer than twenty words. “Solution”: Suppose to the contrary that not every natural number can be so described. Let $ S$ be the set of all natural numbers which are…
Eigenfaces, for Facial Recognition
Math ∩ Programming — 7/27/2011
This post assumes familiarity with the terminology and notation of linear algebra, particularly inner product spaces. Fortunately, we have both a beginner’s primer on linear algebra and a follow-up primer on inner products. The Quest We are on a…
Inner Product Spaces—A Primer
Math ∩ Programming — 7/25/2011
Vector spaces alone are not enough to do a lot of the interesting things we’d like them to do. Since a vector space is a generalization of Euclidean space, it is natural for us to investigate more specific types of vector spaces which are more akin…
Möbius Transformations are Isometries of a Sphere
Math ∩ Programming — 7/23/2011
We present a video on Möbius transformations and the geometry of the sphere. Anyone who has taken or will take complex analysis (that means you engineers!) should watch this. It shows not only the beautiful correspondence between the two, but it…
Hunting Serial Killers
Math ∩ Programming — 7/20/2011
“Tonight’s the Night” A large volume of research goes into the psychological and behavioral analysis of criminals. In particular, serial criminals hold a special place in the imagination and nightmares of the general public (at least, American…
False Proof—The Reals are Countable
Math ∩ Programming — 7/19/2011
It seems that false proofs are quickly becoming some of the most popular posts on Math ∩ Programming. I have been preparing exciting posts on applications of graph coloring, deck stacking, and serial killers. Unfortunately, each requires resources…
False Proof—All Horses are the Same Color
Math ∩ Programming — 7/16/2011
Problem: Show that all horses are of the same color. “Solution”: We will show, by induction, that for any set of $ n$ horses, every horse in that set has the same color. Suppose $ n=1$, this is obviously true. Now suppose for all sets of $ n$…
Graph Coloring, or Proof by Crayon
Math ∩ Programming — 7/15/2011
How many colors are required to color the provinces of Costa Rica? A common visual aid for maps is to color the regions of the map differently, so that no two regions which share a border also share a color. For example, to the right is a map of…
Three Circles and Collinear Centers of Dilation
Math ∩ Programming — 7/13/2011
Problem: Suppose their are three circles in the plane of distinct radii. For any two of these circles, we may find their center of dilation as the intersection point of their common tangents. For example, in the following picture we mark the three…
Optimally Stacking the Deck—Kicsi Poker
Math ∩ Programming — 7/11/2011
A Puzzle is Born Sitting around a poolside table, in the cool air and soft light of a June evening, a few of my old friends and I played a game of Texas Hold ‘Em. While we played we chatted about our times in high school, of our old teachers,…
Set Theory—A Primer
Math ∩ Programming — 7/9/2011
It’s often that a student’s first exposure to rigorous mathematics is through set theory, as originally studied by Georg Cantor. This means we will not treat set theory axiomatically (as in ZF set theory), but rather we will take the definition of…
False Proof—31.5 = 32.5
Math ∩ Programming — 7/7/2011
Problem: Show 31.5 = 32.5. “Solution”: Explanation: It appears that by shifting around the pieces of one triangle, we have constructed a second figure which covers less area! Since the first triangle has base length 13 and height 5, its area is…
False Proof—There are Finitely Many Primes
Math ∩ Programming — 7/5/2011
Problem: Show there are finitely many primes. “Solution”: Suppose to the contrary there are infinitely many primes. Let $ P$ be the set of primes, and $ S$ the set of square-free natural numbers (numbers whose prime factorization has no repeated…
False Proof—1 = 2
Math ∩ Programming — 7/5/2011
“Solution”: Let $ a=b \neq 0$. Then $ a^2 = ab$, and $ a^2 – b^2 = ab – b^2$. Factoring gives us $ (a+b)(a-b) = b(a-b)$. Canceling both sides, we have $ a+b = b$, but remember that $ a = b$, so $ 2b = b$. Since $ b$ is nonzero, we may divide both…
Geometric Series with Geometric Proofs
Math ∩ Programming — 7/5/2011
Problem: $ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots = 1$ Solution: Problem: $ \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots = \frac{1}{2}$ Solution: Problem: $ \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \dots =…
Turing Machines—A Primer
Math ∩ Programming — 7/4/2011
Last time we saw some models for computation, and saw in turn how limited they were. Now, we open Pandrora’s hard drive: Definition: A Turing machine is a tuple $ (S, \Gamma, \Sigma, s_0, F, \tau)$, where $ S$ is a set of states, $ \Gamma$ is a set…
Determinism and Finite Automata—A Primer
Math ∩ Programming — 7/3/2011
The first step in studying the sorts of possible computations (and more interestingly, those things which cannot be computed) is to define exactly what we mean by a “computation.” At a high level, this is easy: a computation is simply a function….
Sums of k Powers
Math ∩ Programming — 7/1/2011
Problem: Prove that for all $ n,k \in \mathbb{N}, k > 1$, we have \(\sum \limits_{i=0}^{n} k^i = \frac{k^{n+1}-1}{k-1}\) Solution: Representing the numbers in base $ k$, we have that each term of the sum is all 0’s except for a 1 in the $ i$th…
Turing Machines and Conway’s Dreams
Math ∩ Programming — 6/30/2011
Additional Patterns Last time we left the reader with the assertion that Conway’s game of life does not always stabilize. Specifically, there exist patterns which result in unbounded cell population growth. Although John Conway’s original…
The Wild World of Cellular Automata
Math ∩ Programming — 6/30/2011
There is a long history of mathematical models for computation. One very important one is the Turing Machine, which is the foundation of our implementations of actual computers today. On the other end of the spectrum, one of the simpler models of…
Tiling a Chessboard
Math ∩ Programming — 6/26/2011
Problem: Take a chessboard and cut off two opposite corners. Is it possible to completely tile the remaining board with 2-by-1 dominoes? Solution: Notice that every domino covers exactly one white tile and one black tile. Counting up the colors, we…
Teaching Mathematics—Graph Theory
Math ∩ Programming — 6/26/2011
Community Service Mathematics is supposed to be a process of discovery. Definitions, propositions, and methods of proof don’t come from nowhere, although after the fact (when presented in a textbook) they often seem to. As opposed to a textbook,…
Area of a Triangle
Math ∩ Programming — 6/24/2011
Problem: What is the area of the triangle within the rectangle? Solution: In a moment of inspiration, we draw the following additional line: Now the answer is obvious. Once we split the rectangle into two smaller rectangles, the sides of the…
Sums of the first n numbers, squares
Math ∩ Programming — 6/24/2011
Problem: Find the sum of the first 1000 natural numbers. Solution: Write the numbers twice as follows: $ \begin{matrix} 1 & + & 2 & + & \dots & + & 999 & + & 1000 \\ 1000 & + & 999 & + & \dots & + & 2 & + & 1 \end{matrix}$ Summing the numbers in…
The Party Problem
Math ∩ Programming — 6/23/2011
Problem: At any party of 1000 people, must there always exist two people at the party who have the same number of friends at the party? For the sake of this problem, one cannot be friends with oneself, and friendship is bidirectional. Solution:…
Number of Games in a Tournament
Math ∩ Programming — 6/23/2011
Problem: 1000 players compete in a tournament. In each round, players are matched with opponents, and the winner proceeds to the next round. If there are an odd number of players in a round, one player chosen at random sits out of that round. What…
Google’s Page Rank—Why it Doesn’t Work Anymore
Math ∩ Programming — 6/21/2011
A Bully By Any Other Name From the New York Times: “Shopping online in late July, Clarabelle Rodriguez typed the name of her favorite eyeglass brand into Google’s search bar. In moments, she found the perfect frames — made by a French company…
Google’s Page Rank—The Final Product
Math ∩ Programming — 6/21/2011
Dangling Nodes and Non-Uniqueness Recall where we left off last time. Given a web $ W$ with no dangling nodes, the link matrix for $ W$ has 1 as an eigenvalue, and if the corresponding eigenspace has dimension 1, then any associated eigenvector…
Featured Posts
Math ∩ Programming — 6/20/2011
My next book will be Practical Math for Programmers Searching for Riemann Hypothesis Counterexamples Linear Programming and Healthy Diets Hybrid Images Bezier Curves and Picasso Correcting Errors in Data
Linear Algebra—A Primer
Math ∩ Programming — 6/19/2011
Story Time Linear algebra was founded around the same time as Calculus (think Leibniz, circa 1700) solely for the purpose of solving general systems of linear equations. The coefficients of a system were written in a grid form, with rows…
Google’s PageRank—A First Attempt
Math ∩ Programming — 6/18/2011
The Web as a Graph The goal of this post is to assign an “importance score” $ x_i \in [0,1]$ to each of a set of web pages indexed $ v_i$ in a way that consistently captures our idea of which websites are likely to be important. But before we can…
Big-O Notation—A Primer
Math ∩ Programming — 6/14/2011
The Quest to Capture Speed Companies and researchers spend hundreds of millions of dollars for the fruits of their algorithms. Whether one is indexing websites on the internet for search, folding proteins, or figuring out which warehouse is the…
Well Orderings and Search
Math ∩ Programming — 6/14/2011
Binary Search Binary search is perhaps the first and most basic nontrivial algorithm a student learns. For the mathematicians out there, binary search is a fast procedure to determine whether a sorted list contains a particular element. Here is a…
Prime Design
Math ∩ Programming — 6/13/2011
The goal of this post is to use prime numbers to make interesting and asymmetric graphics, and to do so in the context of the web design language CSS. Number Patterns For the longest time numbers have fascinated mathematicians and laymen alike….
Google’s PageRank—Introduction
Math ∩ Programming — 6/13/2011
Importance on the Web As a society living in the “Information Age,” it comes as no surprise that we are faced with the task of sorting through vast oceans of content. With the admission that most content is actually junk, we must wisely choose the…