Feed Aggregator
Generated with static-feed-aggregator
Against the Sleep=Boring Analogy
Crooked Timber — 8/20/2024
This is a midsummer short and light hearted post, but I find that Summer is often the time when I am most reminded of my bodily existence, and of how naïve us philosophers are in forgetting (de facto, if not in principle) how much our thoughts and…
Henry James Opposes Wildly Unlikeable Guys
Crooked Timber — 8/20/2024
Henry James: girl, you are so cool and smart, and well-dressed, and beautiful. And I mean this in the least-sexual, but not sassy-gay-best-friend way, exactly, but more like just, your good friend who is also gay? And do you know, that guy is the…
New Work on Gender and Development: Soledad Artiz Prillaman’s The Patriarchal Political Order
Crooked Timber — 8/19/2024
The value of individualism often comes up in attempts to make sense of the elusiveness of women’s empowerment. “Investing in women” has not uniformly yielded either the quick reduction in women’s poverty or the decrease in women’s adherence to…
Book note: Moerdijk and van Oosten, Sets, Models and Proofs
Blog - Logic Matters — 8/19/2024
Back (slowly, slowly) to logical matters. My plan for the rest of the year is to put together a second edition of what is consistently the most downloaded of the Big Red Logic Books (and also, surprisingly, the second-best paperback seller), namely…
Let’s remember how benign the internet can be
Blog - Logic Matters — 8/19/2024
In 2002, when the internet was still in its infancy, the philosopher Bernard Williams wrote: Moreover, the Internet shows signs of creating for the first time what Marshall McLuhan prophesied as a consequence of television, a global village,…
Request open problems in honor of Luca Trevisan
Computational Complexity — 8/19/2024
Request for Open Problems In Memory of Luca TrevisanLuca Trevisan passed away on June 19, 2024 at the age of 52, of cancer.I am putting together an open problems column of open problems in his honor.If you are interested in contributing then please…
Sunday photoblogging: gull
Crooked Timber — 8/18/2024
Infinite-time computable analogues of the universal algorithm, Generalized Computability Theory Workshop, Spain, August 2014
Joel David Hamkins — 8/18/2024
This will be a talk at the Generalized Computability Theory workshop in Castro Urdiales, Spain, a beautiful setting on the sea near Bilbao, 19-23 August 2024. Abstract. I shall present infinite-time computable analogues of the universal algorithm,…
Bernoulli Numbers and the Harmonic Oscillator
The n-Category Café — 8/17/2024
The zeroth Bernoulli number is telling us the energy over temperature of a quantum harmonic oscillator in the high-temperature limit. The rest of the Bernoulli numbers are telling us all the ‘low-temperature corrections’ to the oscillator’s energy…
Galois Theory
The n-Category Café — 8/15/2024
Notes, videos, problems and multiple choice questions for a Galois theory course.
Young men aren’t shifting right …
Crooked Timber — 8/15/2024
… at least in the “Anglosphere” One of the striking features of the racist riots in Britain has been the wide spread of ages among those (nearly all men) convicted so far[1]. This is unusual, since criminal violence of all kinds is most commonly…
Side discussion
Crooked Timber — 8/15/2024
As requested by a couple of commenters, I’ve created a separate thread to discuss the issues raised by commenter “closet conservative” in response to my post on US academia. I’ll moderate, but not participate
Favorite Theorems: Random Oracles
Computational Complexity — 8/14/2024
July EditionThis months favorite theorem is a circuit result that implies the polynomial-time hierarchy is infinite relative to a random oracle, answering an open question that goes back to the 80’s. An Average-Case Depth Hierarchy Theorem for…
Green Border
Crooked Timber — 8/14/2024
I spent yesterday evening watching Agnieszka Holland’s remarkable film “Green Border” which has just been released to streaming in the UK after spending about 30 seconds in cinemas. The episode that provides the film’s context is the 2021 decision…
Confluence in Graph Rewriting
The n-Category Café — 8/14/2024
How to apply the ideas of term rewriting to graph rewriting.
P-Sets in Philosophy
Crooked Timber — 8/13/2024
Earlier this week, I received my contributor copy of The Art of Teaching Philosophy: Reflective Values and Concrete Practices, edited by Brynn Welch.[1] It’s an exciting book, and I’m proud to have gotten to contribute to it. My chapter on advising…
Introduction to Categorical Probability
The n-Category Café — 8/13/2024
Guest post by Utku Boduroğlu, Drew McNeely, and Nico Wittrock
Can you trust LLMs with books? Perplexity vs Chat GPT vs Iain McGilchrist
Proses.ID — 8/13/2024
I was listening to this interview of Iain McGilchrist. He was explaining how the mechanistic metaphors that we often use in our daily lives could…
Skew Monoidal Categories Through Triangulations and Examples
The n-Category Café — 8/12/2024
Guest post by Thea Li and Pablo S. Ocal.
Sunday photoblogging: Cranes
Crooked Timber — 8/11/2024
The combinatorics of Game Shows
Computational Complexity — 8/11/2024
(Inspired by Pat Sajak stepping down from Wheel of Fortune)How many different game show are there? Many. How many could there be?1) Based on Knowledge or something else. Jeopardy is knowledge. Wheel and Deal-No Deal are something else. The oddest…
Prismatic Category Theory
The n-Category Café — 8/10/2024
Guest post by C. B. Aberl� and Rub�n Maldonado.
Waiting for God(b)ot
Proses.ID — 8/10/2024
Story 1: Who plans better? You or LLM? I was watching this interview on Machine Learning Street Talk where Prof Subbarao Kambhapati argued that LLMs…
Fascist violence and the imaginative failure of the Labour government
Crooked Timber — 8/10/2024
Often on a Friday evening, we order a curry from our local “Indian” takeaway. They deliver, but it is easier and quicker for me to walk round and collect, and, anyway, I enjoy chatting to the guy behind the counter. He’s a Man United fan, I’m…
Dimensional Analysis in Algebra and Geometry
The n-Category Café — 8/9/2024
A look at how various mathematicians dealt with the idea that quantities have ‘dimensions’, in the sense of dimensional analysis.
Marshalling the grey cells …
Blog - Logic Matters — 8/8/2024
You now know why I wrapped up work on Introducing Category Theory a bit prematurely, and paperbacked what I frankly admitted was/is a beta version, broadly functional but surely not bug-free. I got an earlier-than-expected slot for my scheduled…
Matrix multiplication doesn’t work like that
The Aperiodical — 8/8/2024
Earlier this week I posted a matrix multiplication worksheet on Mastodon. If you do some of these, you might spot what’s funny about them. For example. [ \Large \begin{bmatrix}\color{navy}{4} & \color{navy}{8}\\color{navy}{2} &…
The not-so-strange shortage of conservative professors
Crooked Timber — 8/8/2024
I have a letter in The Chronicle of Higher Education responding to Steven Teles’ call for more conservative college professors. It’s a shortened version of a longer piece I wrote, which I’m posting here. The fact that conservatives are thin in the…
Webmentions and POSSE improvements
Math ∩ Programming — 8/8/2024
This blog now accepts webmentions. I used webmention.io and webmention.js for live rendering. You can see an example at the end of my old Bezier Curves post. After my initial experiments with POSSE, I’ve made a few improvements to the system. Now…
Actually listening to 10cc.
Crooked Timber — 8/7/2024
Once you know my age my musical tastes as a teenager are very easy to guess. Obviously Dylan, Mitchell, the Kinks and the Beatles – equally obviously not the Stones or the Who. Richard Thompson, Sandy Denny, Fairport, Steeleye Span, Roy Harper, The…
Determing which math problems are hard is a hard problem
Computational Complexity — 8/5/2024
I was wondering what the hardest math problems were, and how to define it. So I googled Hardest Math ProblemsThe first hit is here. The 10 problems given there bring up the question of what is meant by hard?I do not think the order they problems…
Aperiodical News Roundup – June/July 2024
The Aperiodical — 8/5/2024
Here’s a round-up of some news we didn’t cover on the Aperiodical in the last couple of months. Research News In computation news, the fifth Busy Beaver number has been found. This Quanta article gives a good writeup. (via TheHigherGeometer) In…
Carnival of Maths 230
The Aperiodical — 8/5/2024
The next issue of the Carnival of Mathematics, rounding up blog posts from the month of July 2024, is now online at Theorem of the Day. The Carnival rounds up maths blog posts from all over the internet, including some from our own Aperiodical. See…
MLIR — Defining Patterns with PDLL
Math ∩ Programming — 8/4/2024
Table of Contents In this article I’ll show how to use PDLL, a tool for defining MLIR patterns, which itself is built with MLIR. PDLL is intended to be a replacement for defining patterns in tablegen, though there are few public examples of its…
Sunday photoblogging: Dean Lane
Crooked Timber — 8/4/2024
Ethics and Education: Touchy Subject
Crooked Timber — 8/3/2024
I think I’ve mentioned before that the Center of which I am director produces a podcast called Ethics and Education which is about… ethics and education. Just to be clear: the producer/director/voice artist/supremo is Carrie Welsh, and my…
Polynomial dialect and mlir-opt tutorial upstreamed
Math ∩ Programming — 8/3/2024
I’ve been upstreaming a bit of my compiler work to the MLIR project. Yesterday, I merged in a tutorial on mlir-opt, the main debugging tool for running passes on MLIR code. This is roughly the upstreamable parts of my first MLIR tutorial entry,…
What Is Entropy?
The n-Category Café — 8/1/2024
A short book called What is Entropy?
Row ( \sqrt{-1} ) of Pascal’s triangle
The Aperiodical — 7/31/2024
Hi! My name is Colin, and I am a PROPER mathematician now. I’ve made a contribution to the Online Encyclopaedia of Integer Sequences. The OEIS If you don’t know about the OEIS, then congratulations! You’re one of today’s lucky 10,000. Except for…
Fully Homomorphic Encryption in Production Systems
Math ∩ Programming — 7/31/2024
Last update: 2024-08-08T21:56:17-0700 In this living document, I will list all production systems I’m aware of that use fully homomorphic encryption (FHE). For background on FHE, see my overview of the field. If you have any information about…
Troubled by Google Maps Reviews
Crooked Timber — 7/31/2024
We just got home from a wonderful trip to Prague, Budapest, and Krakow. All three cities have a rich history of Jewish communities, and one can visit synagogues, musea, and Jewish cemeteries. We visited a number of them, including the very…
Back, and in reasonable working order …
Blog - Logic Matters — 7/31/2024
With huge thanks to the terrific (and uniformly kind) medical staff at the much admired Royal Papworth Hospital, here I am back home, after needed but non-urgent open-heart surgery, complete with a patched ascending aorta and a new heart valve….
FLT solution annouement had its 31’s anniv was about a month ago. Some poems about FLT NOT from ChatGPT
Computational Complexity — 7/28/2024
On June 21, 1993, at the Issac Newton Institute for Mathematical Science, Andrew Wiles announced that he had proven Fermat’s Last Theorem. That wasn’t quite right- there was a hole in the proof that was later patched up with the help of Richard…
In the future we will all have songs written about us, and it will be Lance’s fault.
Computational Complexity — 7/28/2024
In response to my blog post about how its easier to FIND novelty songs (and other things) than it used to be (see here) Lance showed how easy it is to CREATE a novelty song using AI. He had an AI write lyrics and music for THE BILL, see here.The…
Ben Recht on Meehl’s Philosophical Psychology
Math ∩ Programming — 7/27/2024
Ben Recht, a computer science professor at UC Berkeley, recently wrapped up a 3-month series of blog posts on Paul Meehl’s “Philosophical Psychology.” Recht has a table of contents for his blog series. It loosely tracks a set of lectures that Meehl…
Research, retrieve, and use. Find stuff on the internet for fun
Proses.ID — 7/26/2024
I’m having a little celebration moment right now for my information detective skill. Allow me to share it with you. Earlier this week I saw…
Complexity in Michigan
Computational Complexity — 7/24/2024
Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets,2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasanand 2025 Local Arrangements chair Swastik Kopparty enjoy some tapas.I have a long history with the…
StoryteLLM-ing
Proses.ID — 7/24/2024
I needed to collect all the lessons and tactics from 122 YouTube videos on business storytelling. And I need them fast. Why though? Am I…
Protected: Zyte’s Three Central Questions
Proses.ID — 7/23/2024
There is no excerpt because this is a protected post.
Protected: Experimentory: an exercise in third-person storytelling
Proses.ID — 7/23/2024
There is no excerpt because this is a protected post.
The Big Internet Math-Off 2024, the final!
The Aperiodical — 7/23/2024
Here’s the final match of The Big Internet Math-Off. Over the past month, we’ve heard from 16 interesting mathematicians and whittled them down to just 2. Today, we’re pitting Matt Enlow against Angela Tabiri to determine The World’s Most…
How we might have viewed the continuum hypothesis as a fundamental axiom necessary for mathematics, Oxford Phil Maths seminar, May 2025
Joel David Hamkins — 7/22/2024
This will be a talk for the Philosophy of Mathematics Seminar at the University of Oxford, 19 May 2025. Abstract. I shall describe a simple historical thought experiment showing how our attitude toward the continuum hypothesis could easily have…
The Story of Shor’s Algorithm
Computational Complexity — 7/19/2024
The quantum factoring algorithm of Peter Shor (FOCS 1994, SIAM Review 1999) turns thirty this year. Before his algorithm, quantum computing lacked the killer app, something practical that quantum could do that seems hard for classical computers….
Carnival of Maths 229
The Aperiodical — 7/19/2024
The next issue of the Carnival of Mathematics, rounding up blog posts from the month of June 2024, is now online at Cavmaths. The Carnival rounds up maths blog posts from all over the internet, including some from our own Aperiodical. See…
A musical intermission
Blog - Logic Matters — 7/18/2024
I’m going to be out of commission for a while, as the date for planned surgery has rolled around. Hopefully, I’ll be back in reasonable working order next month. Meanwhile, let’s have a musical intermission, from two of my very favourite pianists…
The Big Internet Math-Off 2024, Semi-final 2
The Aperiodical — 7/18/2024
Here’s the second semi-final match of The Big Internet Math-Off. Today, we’re pitting Angela Tabiri against Ayliean. Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you know any more cool facts…
Frege on seeing what is in front of his nose, revisited
Blog - Logic Matters — 7/17/2024
There’s a new piece just published by Jamie Tappenden with the promising title ‘Following Bobzien: Some Notes on Frege’s Development and Engagement with his Environment’ (History and Philosophy of Logic…
Berdansa dengan keterbatasan
Proses.ID — 7/17/2024
Sadar nggak teman-teman bahwa kita senantiasa berdansa dengan keterbatasan? Hampir semua yang kita lakukan sehari-hari itu sebenarnya adalah salah satu dari antara dua hal ini:…
The Big Internet Math-Off 2024, Semi-final 1
The Aperiodical — 7/17/2024
Here’s the first semi-final match of The Big Internet Math-Off. Today, we’re pitting Fran Herr against Matt Enlow. Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you know any more cool facts about…
Unreasonable breakthroughs
Proses.ID — 7/17/2024
Lately I’ve been revisiting this idea that reason is not the best path to breakthroughs. The core argument is that: we arrive at breakthroughs through…
(Excerpted transcript) Kenneth Stanley on MLST – AI: Is it science or art?
Proses.ID — 7/17/2024
Kenneth Stanley (KS): … there’s this duality…. in the way i think about science and engineering. … the two sides of a coin where scientists…
Summer reading?
Blog - Logic Matters — 7/16/2024
The newspaper culture pages have been full of recommendations for summer reading. Let me add my two-pennyworth on books I’ve recently particularly enjoyed reading or re-reading. I’ve just devoured Rory Stewart’s Politics on the Edge (in the US, How…
Puzzles of reality and infinity, Mindscape Podcast
Joel David Hamkins — 7/15/2024
I was interviewed by Sean Carroll for his Mindscape Podcast, broadcast 15 July 2024.
Skew-Monoidal Categories: Logical and Graphical Calculi
The n-Category Café — 7/15/2024
This blog post applies rewriting methods to the study of skew monoidal categories.
Spicy sleight
Proses.ID — 7/15/2024
Someone once shared a trick with me: if you’re not a great cook but want to sell food, your best bet is to make it…
And then there were five …
Blog - Logic Matters — 7/14/2024
A printed copy of ICT has now arrived. So the fifth Big Red Logic Book — the longest yet — really exists! I’m manfully restraining myself, at least for now, from looking at it too closely, because when I do — a pound to a penny! — I’ll immediately…
The Term Quantum Being Misused … Again
Computational Complexity — 7/14/2024
In a post from 2015 I noted that the word quantum is often misused (see here). Have things gotten better since then? I think you know the answer. But two uses of the word quantum caught my attention1) The episode Subspace Rhapsody of Star Trek-…
How the continuum hypothesis could have been a fundamental axiom
Blog - Logic Matters — 7/13/2024
Like many, I greatly admire Joel Hamkins’s terrific combination of technical prowess and expository ability as a mathematician. I’ve learnt a great deal from him. And I hope to learn more: he is promising us a book on ten ways of proving Gödelian…
The Big Internet Math-Off 2024, Quarter-final 4
The Aperiodical — 7/13/2024
Here’s the last quarter-final match of The Big Internet Math-Off. Today, we’re pitting Ayliean against Dave Richeson. Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you know any more cool facts…
Double Limits: A User’s Guide
The n-Category Café — 7/12/2024
This post introduces limits in double categories
The Big Internet Math-Off 2024, Quarter-final 3
The Aperiodical — 7/12/2024
Here’s the third quarter-final match of The Big Internet Math-Off. Today, we’re pitting Fran Watson against Fran Herr. It’s an extravafranza! Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you…
The epigraph not used …
Blog - Logic Matters — 7/11/2024
I was tempted, just for a moment, to preface all that abstract nonsense, all those higher ramblings, with καὶ παίζειν ὅτε καιρός, ἐπαίξαμεν• ἡνίκα καιρὸς οὐκέτι, λωιτέρης φροντίδος ἁψόμεθα. When it was time for play, we played. Now that is no…
Favorite Theorems: Extracting Ramsey Graphs
Computational Complexity — 7/10/2024
June EditionTwo decades ago, I named the recently departed Luca Trevisan’s paper connecting extractors to psuedorandom generators as one of my favorite theorems from 1995-2004. I’m dedicating this month’s favorite theorem to him.Suppose we have two…
An Operational Semantics of Simply-Typed Lambda Calculus With String Diagrams
The n-Category Café — 7/10/2024
The aim is to use string diagrams to represent simply-typed lambda calculus terms so that computation may be modeled by the idea of a sequence of rewriting steps of string diagrams, providing an operational semantics.
Imprecise Probabilities: Towards a Categorical Perspective
The n-Category Café — 7/9/2024
We discuss some of the limitations that the measure-theoretic probability framework has in handling uncertainty and present some other formal approaches to modelling it, an introduction to the study of imprecise probabilities from a mathematical…
The combinatorics of picking a Vice President
Computational Complexity — 7/8/2024
Trump is pondering who to pick for his vice president. For a recent podcast about it go here. Spoiler alert: Doug B or Marco R or J.D. Vance. In 2008 I did a blog post titled I would bet on INTRADE that INTRADE will do badly picking VP…
Favorite Theorems: Algebraic Circuits
Computational Complexity — 7/6/2024
May EditionMost of my favorite theorems tell us something new about the world of complexity. But let’s not forget the greatest technical challenges in our area: proving separations that are “obviously” true. Here’s the most exciting such result…
Why is called the Turing Award (revisited)?
Computational Complexity — 7/3/2024
Avi Wigderson gave his ACM Turing Award lecture last week, and instead of telling his own story, he focused on Alan Turing and his influence on complexity. If you didn’t see it live, you can watch on YouTube or below.I want to revisit a post I…
How the continuum hypothesis could have been a fundamental axiom
Joel David Hamkins — 7/3/2024
Joel David Hamkins, “How the continuum hypothesis could have been a fundamental axiom,” Mathematics arXiv (2024), arxiv:2407.02463. Continue reading →
Did Turing prove the undecidability of the halting problem?
Joel David Hamkins — 7/2/2024
Joel David Hamkins and Theodor Nenu, “Did Turing prove the undecidability of the halting problem?”, 18 pages, 2024, arxiv:2407.00680. Continue reading →
Technology: 1966, 2006, 2023.
Computational Complexity — 7/1/2024
In 2013 I wrote a blog to celebrate Lance’s 50th birthday by contrasting what things were like when Lance was 10 to when he was 50. That post is here.But life has even changed from 2006 to 2023. I will tell three stories, one from 1966, one from…
E versus EXP
Computational Complexity — 6/27/2024
Why do we have two complexity classes for exponential time, E and EXP?First the definitions:E is the set of problems computable in time (2^{O(n)}).EXP is the set of problems computable in time (2^{\mathrm{poly}(n)}).The nondeterministic…
Detecting field names with C++ metaprogramming
Math ∩ Programming — 6/26/2024
A quick note: you can use C++11 templates to detect struct fields by name and type, and statically branch on them. I first heard of this solution from breeze1990. Say I want to detect if a struct has a field size of type int. Create two template…
Soliciting open problems in honore of Luca T for my Open Problems Column
Computational Complexity — 6/24/2024
As you all know Luca Trevisan, a Giant in our field, passed away at the too-young age of 52. See Lance’s post on Luca HERE. As the editor of the SIGACT News Open Problems Column I am putting together an open problems column in his memory. (I did…
Barycentric Lagrange Interpolation
Math ∩ Programming — 6/21/2024
In my studies of the Remez algorithm, I learned about the barycentric Lagrange interpolation formula. The context is finding a polynomial of degree at most $n$ that passes through $n+1$ points $(x_0, y_0), \dots, (x_n, y_n)$. The classical Lagrange…
Luca Trevisan (1971-2024)
Computational Complexity — 6/20/2024
Complexity theorist Luca Trevisan lost his battle to cancer yesterday in Milan at the age of 52. A terrible loss for our community and our hearts go out to his family. The community will honor Trevisan’s life and legacy 12:30 PM Pacific Time…
Rethinking Heuristica
Computational Complexity — 6/20/2024
I’ve argued that more and more we seem to live in an Optiland, a computational utopia where through recent developments in optimization and learning we can solve the NP-problems that come up in practice and yet cryptography remains unscathed. We…
Magnitude Homology Equivalence
The n-Category Café — 6/18/2024
When do two subsets of Euclidean space have the same magnitude homology?
Should Prover and Verifier have been Pat and Vanna?
Computational Complexity — 6/17/2024
LANCE: I had my first Quanta Article published! I explore computation, complexity, randomness and learning and feeling the machine.BILL: Feels to me like a mashup of old blog posts. Changing topics, I told Darling that you used Pat for Prover and…
100 Papers on Magnitude
The n-Category Café — 6/15/2024
To celebrate the 100th paper on magnitude, a quick rundown of what’s happening in the world of magnitude and which areas are undeservedly underexplored
What is addiction
Abuse of Notation — 6/11/2024
Today’s topic of discussion is addiction. Why do we get addicted? The simple answer is that addictive stuff is pleasurable and we just like to do stuff that is pleasurable, but that’s not complete, e.g. nobody goes to rehab for patting kittens. The…
Is the world discrete or continuous
Abuse of Notation — 6/11/2024
I have always been awed and confused by the apparent divide between number theory and the other algebraic fields of mathematics. Look closely between any two regions of mathematical study and you will find numerous dualities weaving a dense web of…
CFG-Kolm-complexity is singleton sets with Lance and Bill
Computational Complexity — 6/10/2024
For this post all Context Free Grammars (henceforth CFGs) are assumed to be in Chomsky Normal Form. The size of a CFG (G) is the number of rules. We denote this by ( | G | ).BILL: In my automata theory class I want to do some lower bounds on the… |
Mathematics, Philosophy of Set Theory and Infinity, Back to the Stone Age interview, May 2024
Joel David Hamkins — 6/7/2024
I was interviewed by Francesco Cavina for the Back to the Stone Age series on May 17, 2024, with a sweeping discussion of the philosophy of set theory, infinity, the continuum hypothesis, beauty in mathematics, and much more.
Random life updates
Math ∩ Programming — 6/6/2024
I added Twitter syndication, and because I have nothing to test it with I’ll share some random life updates. My daughter was born recently, which means I’m on paternity leave for a few months. Hopefully in the liminal hours of sleep training, I’ll…
The Godzilla Moment
Computational Complexity — 6/6/2024
On the plane earlier this week I got around to watching the Academy Award winning movie Godzilla Minus One, one of the best monster movies I’ve seen set in Japan during the aftermath of World War II, with a pretty emotional substory about a man…
3d Rotations and the 7d Cross Product (Part 2)
The n-Category Café — 6/5/2024
Two ways to get SO(3) to act irreducibly on the imaginary octonions while preserving their cross product.
FOCS 2024 Test of Time Award. Call for nominations and my opinion
Computational Complexity — 6/3/2024
The call for nominations for the Test of Time Award at FOCS 2024 has been posted here.Eligibility and past winners are here.Points1) It is good to have an award that waits until the dust settles and we can see what was really important.2) The…
Daniel Solow Author’s Award 2024
Joel David Hamkins — 5/29/2024
My book, Proof and the Art of Mathematics (MIT Press 2020), has been awarded the 2024 Daniel Solow Author’s Award by the Mathematical Association of America. The MAA asked me to write a brief response to receiving the award… One … Continue reading →
Double Digit Delights
Computational Complexity — 5/29/2024
It started with a post from Fermat’s Library.132 is the sum of all the 2-digit numbers made from its digits. It is the smallest such number. pic.twitter.com/hrByAXbr51— Fermat’s Library (@fermatslibrary) May 26, 2024 My immediate reaction was why…
Life Story of Mathematician & Philosopher of Infinity, interviewed by The Human Podcast, May 2024
Joel David Hamkins — 5/27/2024
I was interviewed by The Human Podcast on 17 May 2024. Please enjoy our sweeping conversation about nature of infinity, the nature of abstract mathematical existence, the applicability of mathematical abstractions to physical reality, and more. At…
National BBQ day vs World Quantum Day
Computational Complexity — 5/26/2024
After my post on different holiDAYS, here, such as Talk like a Pirate Day, and Raegan Revor day, two other Days were brought to my attention1) Lance emailed me about National BBQ day, which is May 16. See here2) While at a Quantum Computing Prelim…
Forcing is simply the iterative conception undertaken with multivalued logic, ForcingFest, Oslo, June 2024
Joel David Hamkins — 5/25/2024
I shall be speaking at the ForcingFest meeting at the University of Oslo, 21 June 2024. Abstract. I will explain how the forcing construction can be seen as a direct implementation of the iterative conception, giving rise to the cumulative ……
The continuum hypothesis could have been a fundamental axiom, CFORS Grad Conference, Oslo, June 2024
Joel David Hamkins — 5/25/2024
I shall be giving a keynote lecture for the CFORS Grad Conference at the University of Oslo, 19-20 June 2024. Abstract. I shall describe a simple historical thought experiment showing how our attitude toward the continuum hypothesis could easily…
Peer Review
Computational Complexity — 5/22/2024
Daniel Lemire wrote a blog post Peer Review is Not the Gold Standard in Science. I wonder who was claiming it was. There is whole section of an online Responsible Conduct in Research we are required to take on peer review which discussing its…
Math databases
Math ∩ Programming — 5/18/2024
Steven Clontz informed me of an effort he’s involved in called code4math. It’s described as a professional organization for the advancement of mathematical research through building non-research software infrastructure. By that he means, for…
Experiments with POSSE
Math ∩ Programming — 5/13/2024
POSSE stands for Publish (on your) Own Site, Syndicate Elsewhere. I first heard about it from Cory Doctorow. I’m experimenting with automation to convert posts tagged shortform into Mastodon threads (I’m mathstodon.xyz/@j2kun). I’m using Hugo as a…
Remez and function approximations
Math ∩ Programming — 5/6/2024
I’ve been learning recently about how to approximate functions by low-degree polynomials. This is useful in fully homomorphic encryption (FHE) in the context of “arithmetic FHE” (see my FHE overview article), where the computational model makes…
The Biome
Good Fibrations — 5/6/2024
We outline connections between the gut microbiome, autoimmune conditions, neuropathic pain, eye pain, chemical intolerance, and a specific set of “overactive” mental illnesses. All seem to be connected to a sensory processing disorder. This is…
A High-Level Technical Overview of Fully Homomorphic Encryption
Math ∩ Programming — 5/4/2024
About two years ago, I switched teams at Google to focus on fully homomorphic encryption (abbreviated FHE, or sometimes HE). Since then I’ve got to work on a lot of interesting projects, learning along the way about post-quantum cryptography,…
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…
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…
Efficient instance resolution for Agda
Amelia’s Blag: Latest articles — 3/8/2024
Translating mathematics into code that a proof assistant can understand is a process that involves a fair bit of friction. There’s quite a big difference between what humans are willing to suspend disbelief about, and what a type checker will…
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…
Airfoil
Bartosz Ciechanowski — 2/27/2024
The dream of soaring in the sky like a bird has captivated the human mind for ages. Although many failed, some eventually succeeded in achieving that goal. These days we take air transportation for granted, but the physics of flight can still be…
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…
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…
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,…
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”.
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)…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
Bicycle
Bartosz Ciechanowski — 3/28/2023
There is something delightful about riding a bicycle. Once mastered, the simple action of pedaling to move forward and turning the handlebars to steer makes bike riding an effortless activity. In the demonstration below, you can guide the rider…
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.
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.
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…
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…
A quickie: Boundaries in Cubical Agda
Amelia’s Blag: Latest articles — 8/29/2022
Wonderfully vague title, yes? As some of you might know, I’m now maintaining the implementation of Cubical Agda. Undoubtedly, if you know, it’s because I’ve been talking your ear off about it: I’m sorry. The “little kid with new toy” energy will…
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.
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,…
The Adjoint Functor Theorem in Everyday Life
Amelia’s Blag: Latest articles — 3/13/2022
Here’s a mathematical situation that comes up a lot more often than is reasonable. Suppose we have some mathematical object GGG, generally defined as some structure on a set: a group, a ring, a topological space. These all have natural categorical…
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!
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 Complete History of isoToEquiv
Amelia’s Blag: Latest articles — 12/17/2021
It’s a standard fact in (higher) category theory and homotopy theory that any equivalence of categories (homotopy equivalence) can be improved to an adjoint equivalence of categories (strong homotopy equivalence). Adjoint equivalences (and strong…
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…
Parsing Layout, or: Haskell’s Syntax is a Mess
Amelia’s Blag: Latest articles — 9/3/2021
Hello! Today we’re going to talk about something I’m actually good at, for a change: writing compilers. Specifically, I’m going to demonstrate how to wrangle Alex and Happy to implement a parser for a simple language with the same indentation…
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…
Cubical Sets
Amelia’s Blag: Latest articles — 6/21/2021
In which I try to write about semantics. This is not gonna go well, but I’m gonna try my best. I’ve heard it on good authority that the best way to learn something is to explain it to someone else, so in this post I’m going to use you, dear reader,…
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…
A quickie: Axiom J
Amelia’s Blag: Latest articles — 6/7/2021
Hey y’all, it’s been three months since my last blog post! You know what that means.. or should mean, at least. Yes, I’d quite like to have another long blog post done, but… Life is kinda trash right now, no motivation for writing, whatever. So…
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…
Cubical Type Theory
Amelia’s Blag: Latest articles — 3/7/2021
Hello, everyone! It’s been a while, hasn’t it? Somehow, after every post, I manage to convince myself that I’m gonna be better and not let a whole season go by between posts, but it never happens. For the last two posts I’ve been going on at length…
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…
On Induction
Amelia’s Blag: Latest articles — 1/15/2021
Last time on this… thing… I update very occasionally, I talked about possible choices for representing equality in type theory. Equality is very important, since many properties of programs and mathematical operators are stated as equalities (e.g.,…
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…
Reflections on Equality
Amelia’s Blag: Latest articles — 10/30/2020
When shopping for a dependent type theory, many factors should be taken into consideration: how inductive data is represented (inductive schemas vs W-types), how inductive data computes (eliminators vs case trees), how types of types are…
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…
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…