# Feed Aggregator

Generated with static-feed-aggregator

## Bye bye, Tories, hello what?

Crooked Timber — 7/5/2024

In the UK, we’re all waking up to the prospect of a new government. The election was an oddity: Labour has converted a modest 35% vote share into a whopping Parliamentary majority; the Tories did somewhat better than suggested, on around 24%, but…

## The Big Internet Math-Off 2024, Round 1, Match 5

The Aperiodical — 7/5/2024

Here’s the fifth match in Round 1 of The Big Internet Math-Off. Today, we’re pitting Matt Peperell against Fran Watson. 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…

## The Big Internet Math-Off 2024, Round 1, Match 4

The Aperiodical — 7/4/2024

Here’s the fourth match in Round 1 of The Big Internet Math-Off. Today, we’re pitting Mats Vermeeren against Howie Hua. 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…

## Does Social Media Cause Anything?

Crooked Timber — 7/3/2024

In the 18 months since I quit Twitter, I can feel the atrophy of my vibe detector. I’m reading more than ever, on Substack and the FT, Discord and group chats — much of the same “content” I would’ve encountered on Twitter, in fact, but without the…

## 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 →

## The Big Internet Math-Off 2024, Round 1, Match 3

The Aperiodical — 7/3/2024

Here’s the third match in Round 1 of The Big Internet Math-Off. Today, we’re pitting Matt Enlow against Sam Kay. 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…

## Supreme Court Rules Hitler Immune from Prosecution for Burning Down Reichstag, Seizing Absolute Power

Crooked Timber — 7/2/2024

If the current Supreme Court had held comparable office in Weimar Germany, that is, its opinion in Trump v. United States would have rendered the judgment in this post’s headline. Never mind that the Weimar Constitution was different from the U.S….

## Advice on faculty job application letters

Crooked Timber — 7/2/2024

I’m hosting a couple of professionalization discussions for our PhD candidates and postdocs this summer, informal conversations to help them navigate the crazy academic job market. A few weeks ago we discussed job talks as the department had just…

## The Big Internet Math-Off 2024, Round 1, Match 2

The Aperiodical — 7/2/2024

Here’s the second match in Round 1 of The Big Internet Math-Off. Today, we’re pitting Angela Tabiri against Max Hughes. 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…

## Three bits about seeing and looking

Proses.ID — 7/2/2024

Being seen vs being looked at I recently saw this video where they discussed about the distinction between being seen and being looked at. Never…

## Flow inducing activities

Proses.ID — 7/2/2024

Thought of some activities that facilitate Flow state, bring you to the present moment, engage your whole self (mind, body, soul) playing music playing sports…

## 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 →

## Introducing Category Theory — a full draft, at last!

Blog - Logic Matters — 7/1/2024

There is now, at last, a full draft of Introducing Category Theory. You can download the PDF here. The second half still needs more proof-reading and needs indexing. But I don’t envisage adding significantly to the content. After all — rather…

## The Big Internet Math-Off 2024, Round 1, Match 1

The Aperiodical — 7/1/2024

It’s math-off time! Here’s the first match in this year’s Big Internet Math-Off. Today, we’re pitting Katie Steckles against Benjamin Dickman. Take a look at both pitches, vote for the bit of maths that made you do the loudest “Aha!”, and if you…

## 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…

## Sunday photoblogging: good morning!

Crooked Timber — 6/30/2024

Sometimes you have to go looking for photos, but this is what greeted me when I got up to make the coffee the other morning.

## 4. Prime-number Pattern

The Aperiodical — 6/28/2024

I’m slowly working to (sort of) recreate Martin Gardner’s cover images from Scientific American, the so-called Gardner’s Dozen. This time it’s the turn of the March 1964 issue. In the article ‘The remarkable lore of the prime numbers’, later…

## Occasional paper: On the curious diet of the Speckled Mousebird

Crooked Timber — 6/28/2024

So my wife took this picture in our garden yesterday, here in Kigali, Rwanda: Take a close look. This little bird — about the size of an American cardinal, or a European robin — is facing us. It’s also facing the sun, though you can’t see that….

## Postcard from Aldeburgh

Blog - Logic Matters — 6/27/2024

A few days away, staying in a familiar cottage near Aldeburgh, less than two hours from home. And the best weather we have ever had here. Usually, at least in our memory, it is windswept and intermittent rain: this time, warm sun and welcome…

## 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…

## Danger, discomfort, and growth

Proses.ID — 6/27/2024

Hi friends, welcome back. In the first part, we looked at the extent of painful and pleasurable sensations. We also split pain into two camps:…

## Pain and pleasure, discomfort and danger

Proses.ID — 6/27/2024

I want to talk about pain, pleasure, danger, discomfort, and suffering. It started when I realised how temporary some painful physical sensations are and how…

## 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…

## I feel lost and bored with life

Proses.ID — 6/25/2024

A friend was telling me about how he is “bored” with life. He goes to work, maintains his open source project as a hobby, helps…

## RE:Language is primarily a tool for communication rather than thought

Proses.ID — 6/24/2024

I just saw someone on my Facebook timeline proudly shared about how he “made a ruckus” on some online scientific forum because he challenged the…

## 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…

## Religious impulse runs deep

Proses.ID — 6/23/2024

In the previous post in this series, I explored the question is there no reason to believe in god? As I followed the thought, the…

## The magic of shared languages.

Proses.ID — 6/23/2024

Hi friends, how are you? I was just thinking of a couple of funny stories of when my mother cutely used the wrong words that…

## Sunday photoblogging: Narbonne Cathedral (2015)

Crooked Timber — 6/23/2024

## 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…

## No reasons to believe in god (Religious Impulse part 1)

Proses.ID — 6/21/2024

I saw this video recently https://www.instagram.com/reel/C48KLH0u-Zl/ When the lady said “_I did not see reason to believe that there was a god__”, I realised I…

## Occasional paper: Fungal banking

Crooked Timber — 6/20/2024

So in the last couple of decades we’ve discovered that many plants rely on networks of soil fungi to bring them critical trace nutrients. This is a symbiotic relationship: the fungal network can access these nutrients much better than plants can,…

## 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…

## Announcing the Big Internet Math-Off 2024

The Aperiodical — 6/19/2024

In 2018 I ran a just-for-fun competition to find “The World’s Most Interesting Mathematician”. It was so much fun that I ran it again in 2019 and 2020. And then big things happened in my life and the wider world and I haven’t had the energy to do…

## From Zero to Hero: a Euclidean proof

The Aperiodical — 6/18/2024

It used to live, unloved, in the A-level formula book: a mysterious result relating the area of a triangle to its sides. The most interesting thing about it was its name: Heron’s formula. (As far as I can make out, the chap’s name was Hero of…

## Aperiodical News Roundup – May 2024

The Aperiodical — 6/18/2024

Here’s a round-up of some of the mathematical news we saw last month. Maths News Thomas Hales and Koundinya Vajjha have claimed a proof of Mahler’s first conjecture, that the most unpackable centrally symmetric convex disk in the plane is a…

## 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…

## Back to the Study Guide?

Blog - Logic Matters — 6/16/2024

I’m almost done with the category theory book — at least as far as the draft content is concerned. There will be tinkering to be done (in particular with respect to having a consistent line on issues of “size”), and then there will be the joys of…

## Sunday photoblogging: Iceland (2011)

Crooked Timber — 6/16/2024

## Waiting for the nova

Crooked Timber — 6/16/2024

“You’re always building models. Stone circles. Cathedrals. Pipe-organs. Adding machines. I got no idea why I’m here now, you know that? But if the run goes off tonight, you’ll have finally managed the real thing.” “I don’t know what you’re talking…

## 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

## Particularly mathematical Birthday Honours 2024

The Aperiodical — 6/15/2024

The UK Government have announced the new set of King’s Birthday Honours. Here’s our selection of particularly mathematical entries for this year. If you spot any more, let us know in the comments and we’ll add to the list. Get the full list from…

## The edge of extinction

Crooked Timber — 6/14/2024

Referring back to this 2002 post defining “neoliberalism”, I find the claim that the “The (UK) Conservative party is hovering on the edge of extinction”. That wasn’t one of my more accurate assessments, and I’m bearing it in mind when I look at…

## Favorite Theorems: Algebraic Circuits

Computational Complexity — 6/13/2024

Most 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 from the past…

## Macron’s gamble and the myth of the Republican Barrier

Crooked Timber — 6/12/2024

Emmanuel Macron’s decision to call legislative elections in France, following a strong showing for the extreme-right-wing Rassemblement National of Marine Le Pen constitutes an extreme risk. No doubt he thinks that either the RN will fail to get as…

## Boris Giltburg and the Pavel Haas play Brahms

Blog - Logic Matters — 6/11/2024

We had tickets for the Sunday morning Wigmore Hall concert with the Pavel Haas Quartet playing Smetana and Janacek, our first post-Covid occasion to see them play live. But, so it turned out, there were no trains from Cambridge North that morning….

## On Student protests and academic freedom

Crooked Timber — 6/11/2024

In an earlier post (here), prompted by some writings by Jacob T. Levy, I defended the idea that student protests can fall under academic freedom. My argument for this starts from the fact that while many universities can have mission specific…

## 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… |

## Sunday photoblogging: wisteria at Iford

Crooked Timber — 6/9/2024

## The shape of categorial things to come

Blog - Logic Matters — 6/8/2024

The headline news: there is now a new version of my category theory notes, in one document, as Introducing Category Theory, available here. In more detail: I’ve decided against my previous plan of two volumes, in part because there just wasn’t a…

## 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…

## Engaging Erik Olin Wright: Between Class Analysis and Real Utopias

Crooked Timber — 6/6/2024

It’s more than 5 years since Erik died which, for those who knew him, is quite hard to believe, as he is still a strong voice in many of our heads. Because I know many of our readers knew and admired him or his work (or both!) I thought I’d let you…

## 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…

## Lea Desdandre and Thomas Dunford, again

Blog - Logic Matters — 6/3/2024

Lea Desdandre and Thomas Dunford in Mantua … With Mantua looking wonderful, and Lea too, and she and Thomas (it goes without saying) musically stunning as always. Hugely enjoyable (even if you can’t follow the German voice-over). The post Lea…

## Another round with ChatGPT

Blog - Logic Matters — 6/2/2024

ChatGPT is utterly unreliable when it comes to reproducing even very simple mathematical proofs. It is like a weak C-grade student, producing scripts that look like proofs but mostly are garbled or question-begging at crucial points. Or at least,…

## Jensen Huang doesn’t do 1:1s

Proses.ID — 5/31/2024

There’s this clip going around of Jensen Huang being interviewed by Patrick Collison in a Stripe corporate event talking about how he doesn’t do 1:1s.…

## Lanthanides and the Exceptional Lie Group G_{2}

The n-Category Café — 5/30/2024

What the connection between the 14 lanthanide elements and the exceptional Lie group G2?

## 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…

## Climate change

Blog - Logic Matters — 5/28/2024

Some years ago, the University Botanic Gardens here in Cambridge started a special area for the interest of local gardeners, displaying plants particularly tolerant of the low local rainfall. Because this part of East Anglia officially counted as a…

## 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…

## Wild Knots are Wildly Difficult to Classify

The n-Category Café — 5/26/2024

Wild knots are wildly difficult to classify. This is a theorem.

## 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…

## 3d Rotations and the 7d Cross Product (Part 1)

The n-Category Café — 5/23/2024

Apparently there’s an SO(3) subgroup of the automorphism group of the octonions that acts irreducibly on the imaginary octonions.

## 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…

## I don’t do that well when the Jeopardy category is Math

Computational Complexity — 5/20/2024

Bill and Darling are watching Jeopardy.DARLING: Bill, one of the categories is MATH TALK. You will kick butt!BILL: Not clear. I doubt they will have the least number n such that R(n) is not known. They will ask things easy enough so that my math…

## 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…

## Jim Simons (1938-2024)

Computational Complexity — 5/15/2024

Jim Simons passed away Friday at the age of 86. In short he was a math professor who quit to use math to make money before it was fashionable and used part of his immense wealth to start the Simons Foundation to advance research in mathematics and…

## 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…

## What is Closed Form? The Horse Numbers are an illustration

Computational Complexity — 5/12/2024

In the book Those Fascinating Numbers by Jean-Marie De Konick they find interesting (or `interesting’) things to say about many numbers. I reviewed the book in a SIGACT News book review column here. The entry for 13 is odd: 13 is the third Horse…

## Favorite Theorems: Dichotomy

Computational Complexity — 5/8/2024

A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a setting of the variables that make all the constraints true. In CNF-Satisfiability the variables are Boolean and the…

## Two category theory books

Blog - Logic Matters — 5/8/2024

One of the best freely available sets of lecture notes on category theory available is the one by Paulo Perrone, which can be downloaded from the arXiv here. He has now turned these notes into a printed book, Starting Category Theory from World…

## 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…

## May the fourth be with you. Too many -days?

Computational Complexity — 5/6/2024

(This post was inspired by Rachel F, a prior REU-CAAR student, emailing me wishing me a happy Star Wars Day.) I am writing this on May 4 which is Star Wars day. Off the top of my head I know of the following special days (I exclude official…

## 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…

## Lea Desandre and Thomas Dunford

Blog - Logic Matters — 5/4/2024

This is sheer delight. Lea Desandre and Thomas Dunford in concert, recorded in January. The post Lea Desandre and Thomas Dunford appeared first on Logic Matters.

## Line Bundles on Complex Tori (Part 4)

The n-Category Café — 5/4/2024

Today I’ll head toward an explicit bijection between principal polarizations of the Eisenstein surface and centers of hexagons in the hexagonal tiling honeycomb. I won’t quite get there, but I’ll lay the groundwork.

## Line Bundles on Complex Tori (Part 5)

The n-Category Café — 5/4/2024

We prove the main conjecture from last time: a description of the hexagonal tiling lattice using Eisenstein integers.

## 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,…

## Our Obsession with Proofs

Computational Complexity — 5/1/2024

Bullinger’s post on this blog last week focused on Vijay Vazirani’s public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why does Vijay, and theoretical computer science in general, obsess over proofs? You can’t…

## Math Thoughts Inspired by the TV show Succession

Computational Complexity — 4/29/2024

I watched Succession one-episode-a-day on treadmill for 39 days. I’m glad I did this in 2023 since Season 2 aired its last show on Oct 19, 2019, and Season 3 had its first show on Oct 17, 2021, so I would have been in suspense (or at least as much…

## Line Bundles on Complex Tori (Part 3)

The n-Category Café — 4/28/2024

Today I’ll compute the Néron–Severi group of a very symmetrical abelian surface built from the Eisenstein integers. Then I’ll begin to explain a nice picture of a ‘slice’ of this group.

## Is Persistence an Anachronism?

Computational Complexity — 4/24/2024

Guest post by Martin BullingerVery recently, Vijay Vazirani’s paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted to Mathematics of Operations Research. For the first time, it gives a complete and…

## Moving On From Kent

The n-Category Café — 4/23/2024

Kent Philosophy comes to an end

## Intelligent Comments on Bill’s G.H. Hardy/Avi W post that we did not post.

Computational Complexity — 4/21/2024

I posted (see here) about Avi Wigderson being a counterexample to two of G.H. Hardy’s opinions:1) Hardy thought Math was a young man’s game. I got some good comments on this. Some agreed and some disagreed. 2) Hardy thought applied math is dull. I…

## The Modularity Theorem as a Bijection of Sets

The n-Category Café — 4/20/2024

Bruce Bartlett floats a version of the Modularity Theorem for elliptic curves that frames it as an explicit bijection between sets, and has a question for the experts.

## Favorite Theorems: Quantum Provers

Computational Complexity — 4/19/2024

For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier, then two entangled provers can convince a polynomial-time verifier.MIP* =…

## The Quintic, the Icosahedron, and Elliptic Curves

The n-Category Café — 4/18/2024

Bruce Bartlett has a new expository article on “The quintic, the icosahedron, and ellliptic curves”.

## Pythagorean Triples and the Projective Line

The n-Category Café — 4/17/2024

How pondering Pythagorean triples leads us into the algebraic geometry of conics.

## Avi Wigderson is a counterexample to TWO stupid thoughts of G.H. Hardy

Computational Complexity — 4/15/2024

Recently1) Avi Wigderson won the Turing Award (See blog posts by Fortnow-here, Scott-here, Lipton-Regan here, and the ACM announcement here). The last time I could find when Fortnow-Gasarch, Scott, Lipton-Regan all blogged on the same topic was…

## Semi-Simplicial Types, Part II: The Main Results

The n-Category Café — 4/15/2024

Part 2 of a 3-part series about displayed type theory and semi-simplicial types.

## Machine Learning Jobs for Category Theorists

The n-Category Café — 4/11/2024

Symbolica is hiring category theorists. It’s already hired some, and there are job ads for 6 more. They are hiring in the UK and Australia.

## 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…

## 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,…

## 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”.

## The Gödel incompleteness phenomenon, interview with Rahul Sam

Joel David Hamkins — 1/14/2024

Please enjoy my conversation with Rahul Sam for his podcast, a sweeping discussion of topics in the philosophy of mathematics—potentialism, pluralism, Gödel incompleteness, philosophy of set theory, large cardinals, and much more.

## Half Haunted: The 1/2 in Harish-Chandra via the Fourier Transform

Good Fibrations — 12/31/2023

This post is written together with Josh Mundinger. Last time, we compared the Harish-Chandra isomorphism (Z(U\mathfrak g) \cong (\text{Sym} \mathfrak h)^{W,\cdot}) for (\mathfrak g= \mathfrak{sl}_2) to the Duflo isomorphism (Z(U\mathfrak g)…

## Pluralism in the foundations of mathematics, ASL invited address, joint APA/ASL meeting, New York, January 2024

Joel David Hamkins — 12/18/2023

This will be an invited ASL address at the joint meeting of the ASL with the APA Eastern Division conference, held in New York 15-18 January 2024. My talk will be 16 January 2024 11:00 am. Abstract. I shall give … Continue reading →

## The computable model theory of forcing, Rutgers Logic Seminar, December 2023

Joel David Hamkins — 11/23/2023

This will be a talk for the Rutgers University Logic Seminar, December 4, 2023. Abstract. I shall discuss the computable model theory of forcing. To what extent can we view forcing as a computational process on the models of set … Continue reading →

## MLIR — A Global Optimization and Dataflow Analysis

Math ∩ Programming — 11/15/2023

Table of Contents In this article we’ll implement a global optimization pass, and show how to use the dataflow analysis framework to verify the results of our optimization. The code for this article is in this pull request, and as usual the commits…

## 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…

## MLIR — Using Tablegen for Passes

Math ∩ Programming — 8/10/2023

Table of Contents In the last article in this series, we defined some custom lowering passes that modified an MLIR program. Notably, we accomplished that by implementing the required interfaces of the MLIR API directly. This is not the way that…

## MLIR — Writing Our First Pass

Math ∩ Programming — 8/10/2023

Table of Contents This series is an introduction to MLIR and an onboarding tutorial for the HEIR project. Last time we saw how to run and test a basic lowering. This time we will write some simple passes to illustrate the various parts of the MLIR…

## MLIR — Running and Testing a Lowering

Math ∩ Programming — 8/10/2023

Table of Contents Last time, we covered a Bazel build system setup for an MLIR project. This time we’ll give an overview of a simple lowering and show how end-to-end tests work in MLIR. All of the code for this article is contained in this pull…

## MLIR — Getting Started

Math ∩ Programming — 8/10/2023

Table of Contents As we announced recently, my team at Google has started a new effort to build production-worthy engineering tools for Fully Homomorphic Encryption (FHE). One focal point of this, and one which I’ll be focusing on as long as Google…

## Google’s Recent FHE work, and starting HEIR

Math ∩ Programming — 8/10/2023

Today my team at Google published an article on Google’s Developers Blog with some updates on what we’ve been doing with fully homomorphic encryption (FHE). There’s fun stuff in there, including work on video processing FHE, compiling ML models to…

## Variations on Weihrauch degrees (CiE 2023)

Mathematics and Computation — 7/28/2023

I gave a talk “Variations on Weihrauch degrees” at Computability in Europe 2023, which took place in Tbilisi, Georgia. The talk was a remote one, unfortunately. I spoke about generalizations of Weihrauch degrees, a largely unexplored territory that…

## Continuity principles and the KLST theorem

Mathematics and Computation — 7/19/2023

On the occasion of Dieter Spreen’s 75th birthday there will be a Festschrift in the Journal of Logic and Analysis. I have submitted a paper “Spreen spaces and the synthetic Kreisel-Lacombe-Shoenfield-Tseitin theorem”, available as a preprint…

## Two’s Complement and Group Theory

Math ∩ Programming — 7/10/2023

Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the second was the two’s complement representation of a negative…

## Isomorphism invariance and isomorphism reflection in type theory (TYPES 2023)

Mathematics and Computation — 6/15/2023

At TYPES 2023 I had the honor of giving an invited talk “On Isomorphism Invariance and Isomorphism Reflection in Type Theory” in which I discussed isomorphism reflection, which states that isomorphic types are judgementally equal. This strange…

## The Nix, OpenGL and Ubuntu Integration Nightmare

AlternativeBit — 4/20/2023

In this article, we’re about to dive into the uncharted OpenGL on Linux waters. After briefly explaining how the OpenGL calls are routed from your application to the GPU, we’ll look at the NixOS special case. We’ll then explore how we can run the…

## We’re Knot Friends

Math ∩ Programming — 4/1/2023

It’s April Cools again. For a few summers in high school and undergrad, I was a day camp counselor. I’ve written before about how it helped me develop storytelling skills, but recently I thought of it again because, while I was cleaning out a…

## New Video Podcast: fAQ

Math3ma — 3/28/2023

In a bit of fun news, I’ve just launched a new video podcast with my coworker Adam Green. This new video series, which we’re calling fAQ, consists of casual conversations between me and Adam on basic ideas in quantum physics and eventually some…

## What is Superposition, Really?

Math3ma — 3/28/2023

The next episode in the fAQ video podcast is now up! As mentioned last time, this is a new project I’ve embarked on with Adam Green where we chat about different ideas in quantum physics and (at some point) AI. Our primary goal is simply to help…

## 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.

## Exploring strange new worlds of mathematics

Mathematics and Computation — 2/10/2023

On February 10, 2023, I gave my Levi L. Conant Lectur Series talk “Exploring strange new worlds of mathematics”, at the math department of Worcester Polytechnic Institute. Here are the slides with speaker notes and the video recording of the talk.

## A New Perspective of Entropy

Math3ma — 1/10/2023

Hello world! Last summer I wrote a short paper entitled “Entropy as a Topological Operad Derivation,” which describes a small but interesting connection between information theory, abstract algebra, and topology. I blogged about it here in June…

## The Yoneda Lemma

Math3ma — 1/1/2023

Welcome to our third and final installment on the Yoneda lemma! In the past couple of weeks, we’ve slowly unraveled the mathematics behind the Yoneda perspective, i.e. the categorical maxim that an object is completely determined by its…

## Estimating the Security of Ring Learning with Errors (RLWE)

Math ∩ Programming — 12/28/2022

This article was written by my colleague, Cathie Yun. Cathie is an applied cryptographer and security engineer, currently working with me to make fully homomorphic encryption a reality at Google. She’s also done a lot of cool stuff with zero…

## Negacyclic Polynomial Multiplication

Math ∩ Programming — 12/9/2022

In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in…

## Polynomial Multiplication Using the FFT

Math ∩ Programming — 11/16/2022

Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): “"”Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. “”” deg1 =…

## Happy birthday, Dana!

Mathematics and Computation — 10/11/2022

Today Dana Scott is celebrating the 90th birthday today. Happy birthday, Dana! I am forever grateful for your kindness and the knowledge that I received from you. I hope to pass at least a part of it onto my students. On the occasion Steve Awodey…

## Carnival of Mathematics #209

Math ∩ Programming — 10/2/2022

Welcome to the 209th Carnival of Mathematics! 209 has a few distinctions, including being the smallest number with 6 representations as a sum of 3 positive squares: $$\begin{aligned}209 &= 1^2 + 8^2 + 12^2 \\ &= 2^2 + 3^2 + 14^2 \\ &= 2^2 + 6^2 +…

## Key Switching in LWE

Math ∩ Programming — 8/29/2022

Last time we covered an operation in the LWE encryption scheme called modulus switching, which allows one to switch from one modulus to another, at the cost of introducing a small amount of extra noise, roughly $\sqrt{n}$, where $n$ is the…

## Modulus Switching in LWE

Math ∩ Programming — 7/16/2022

The Learning With Errors problem is the basis of a few cryptosystems, and a foundation for many fully homomorphic encryption (FHE) schemes. In this article I’ll describe a technique used in some of these schemes called modulus switching. In brief,…

## One syntax to rule them all

Mathematics and Computation — 5/20/2022

I am at the Syntax and Semantics of Type Theory workshop in Stockholm, a kickoff meeting for WG6 of the EuroProofNet COST network, where I am giving a talk “One syntax to rule them all” based on joint work with Danel Ahman.

## “Practical Math” Preview: Collect Sensitive Survey Responses Privately

Math ∩ Programming — 5/14/2022

This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production Software. Tip: Determine an aggregate statistic about a sensitive question, when survey respondents do not trust that their…

## Cocktails

Math ∩ Programming — 4/1/2022

It’s April Cools! We’re taking back April Fools. When I was younger I had a strange relationship with alcohol, not because of any sort of trauma, but because I found it decidedly boring and disgusting to the taste. I didn’t drink in high school,…

## Nix Substitution: the Way Forward

AlternativeBit — 3/31/2022

Abstract Nix and Guix have the unfortunate reputation to require a lot of bandwidth to distribute software. This reputation is sadly grounded. It seems like explicitly pointing to your dependencies comes with an overhead cost in terms of download…

## Silent Duels—Constructing the Solution part 2

Math ∩ Programming — 3/24/2022

Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Silent Duels—Constructing the Solution part 1 Since it’s been three years since the last post in this series, and the reason for the…

## My next book will be “Practical Math for Programmers”

Math ∩ Programming — 3/16/2022

tl;dr: I’m writing a new book, sign up for the announcements mailing list. I’ve written exactly zero new technical blog posts this year because I’ve been spending all my writing efforts on my next book, Practical Math for Programmers (PMFP,…

## Stop Staring and Compute! Automorphism Groups of Rational Curves

Good Fibrations — 2/23/2022

Let’s compute the automorphism groups of some curves. Often presented as an insurmountable task, we must couragously go forward. There are many ways to do this! We will be using 3 different algorithms, so choose according to your taste. If you do…

## Introducing The Math3ma Institute

Math3ma — 2/22/2022

Today I’m happy to share that the Math3ma platform has recently grown in a small yet personal way. This new endeavor is in its early stages, but it is one that is close to my heart and gives life to the reasons I started this blog six years ago. A…

## Two new doctors!

Mathematics and Computation — 1/12/2022

Within a month two of my students defended their theses: Dr. Anja Petković Komel just before Christmas, and Dr. Philipp Haselwarter just yesterday. I am very proud of them. Congratulations!

## The Gadget Decomposition in FHE

Math ∩ Programming — 12/11/2021

Lately I’ve been studying Fully Homomorphic Encryption, which is the miraculous ability to perform arbitrary computations on encrypted data without learning any information about the underlying message. It’s the most comprehensive private computing…

## Chu are you?

mathematical fantasies — 11/6/2021

What the heck is a Chu space? And whatever it is, does it really belong with all the rich mathematical structures we know and love? Say you have some stuff. What can you do with it? Maybe it’s made of little pieces, and you can do a different thing…

## Math3ma: Behind the Scenes (3B1B Podcast)

Math3ma — 11/1/2021

I recently had the pleasure of chatting with Grant Sanderson on the 3Blue1Brown podcast about a variety of topics, including what first drew me to math and physics, my time in graduate school, thoughts on category theory, basketball, and lots more….

## Group Actions and Hashing Unordered Multisets

Math ∩ Programming — 10/14/2021

I learned of a neat result due to Kevin Ventullo that uses group actions to study the structure of hash functions for unordered sets and multisets. This piqued my interest because a while back a colleague asked me if I could think of any…

## Language, Statistics, & Category Theory, Part 3

Math3ma — 9/27/2021

Welcome to the final installment of our mini-series on the new preprint “An Enriched Category Theory of Language,” joint work with John Terilla and Yiannis Vlassopoulos (https://arxiv.org/abs/2106.07890). Last time we discussed a way to assign sets…

## Carnival of Mathematics #197

Math ∩ Programming — 9/1/2021

Welcome to the 197th Carnival of Mathematics! 197 is an unseemly number, as you can tell by the Wikipedia page which currently says that it has “indiscriminate, excessive, or irrelevant examples.” How deviant. It’s also a Repfigit, which means if…

## Monotone Convergence Theorem

Math3ma — 8/16/2021

Fatou’s Lemma, the Monotone Convergence Theorem, and the Dominated Convergence Theorem are three major results in the theory of Lebesgue integration which, when given a sequence of functions ${f_n}$ answer the question, “When can I switch the…

## Dominated Convergence Theorem

Math3ma — 8/16/2021

Fatou’s Lemma, the Monotone Convergence Theorem, and the Dominated Convergence Theorem are three major results in the theory of Lebesgue integration which, when given a sequence of functions ${f_n}$, answer the question, “When can I switch the…

## The Borel-Cantelli Lemma

Math3ma — 8/16/2021

Today we’re chatting about the Borel-Cantelli Lemma. When I first came across this lemma, I struggled to understand what it meant “in English.” What does $\mu(\cup\cap E_k)=0$ really signify?? There’s a pretty simple explanation if $(X,\Sigma,\mu)$…

## Entropy + Algebra + Topology = ?

Math3ma — 7/28/2021

Today I’d like to share some math connecting ideas from information theory, algebra, and topology. It’s all in a new paper I’ve recently uploaded to the arXiv (https://arxiv.org/abs/2107.09581), which describes a correspondence between Shannon…

## Language, Statistics, & Category Theory, Part 2

Math3ma — 7/21/2021

Part 1 of this mini-series opened with the observation that language is an algebraic structure. But we also mentioned that thinking merely algebraically doesn’t get us very far. The algebraic perspective, for instance, is not sufficient to describe…

## Language, Statistics, & Category Theory, Part 1

Math3ma — 7/7/2021

In the previous post I mentioned a new preprint that John Terilla, Yiannis Vlassopoulos, and I recently posted on the arXiv. In it, we ask a question motivated by the recent successes of the world’s best large language models: “What’s a mice…

## A Nod to Non-Traditional Applied Math

Math3ma — 6/29/2021

What is applied mathematics? The phrase might bring to mind historical applications of analysis to physical problems, or something similar. I think that’s often what folks mean when they say “applied mathematics.” And yet there’s a much broader…

## Linear Algebra for Machine Learning

Math3ma — 6/25/2021

The TensorFlow channel on YouTube recently uploaded a video I made on some elementary ideas from linear algebra and how they’re used in machine learning (ML). It’s a very nontechnical introduction — more of a bird’s-eye view of some basic concepts…

## Warming Up to Enriched Category Theory, Part 2

Math3ma — 6/17/2021

Let’s jump right in to where we left off in part 1 of our warm-up to enriched category theory. If you’ll recall from last time, we saw that the set of truth values ${0, 1}$ and the unit interval $[0,1]$ and the nonnegative extended reals…

## Searching for RH Counterexamples — Exploring Data

Math ∩ Programming — 6/14/2021

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up Productionizing In the last article we added a…

## Warming Up to Enriched Category Theory, Part 1

Math3ma — 6/10/2021

It’s no secret that I like category theory. It’s a common theme on this blog, and it provides a nice lens through which to view old ideas in new ways — and to view new ideas in new ways! Speaking of new ideas, my coauthors and I are planning to…

## The Fibonacci Sequence as a Functor

Math3ma — 6/8/2021

Over the years, the articles on this blog have spanned a wide range of audiences, from fun facts (Multiplying Non-Numbers), to undergraduate level (The First Isomorphism Theorem, Intuitively), to graduate level (What is an Operad?), to research…

## TfE: What Kind of Computational Process is a Mind?

DEONTOLOGISTICS — 5/21/2021

Here’s a thread from the end of last year trying to reframe the core question of the computational theory of mind. I’m still not entirely happy with the arguments sketched here, but it’s a good introduction to the way I think we should articulate…

## webcomic: re-search

Good Fibrations — 5/15/2021

Please enjoy my webcomic on what it feels like to run into a concept for the first time. I will be updating panel by panel, adding each one to this post as I make them. Here begins the adventures of Massey into the unknown.

## TfE: The History of Metaphysics and Ontology

DEONTOLOGISTICS — 5/5/2021

If there’s a subject I’m officially an expert on, it’s what you might call the methodology of metaphysics: the question of what metaphysics is and how to go about it. I wrote my thesis on the question of Being in Heidegger’s work, trying to…

## Meet the New Blog, Same as the Old Blog

DEONTOLOGISTICS — 5/3/2021

For those of you who haven’t already noticed, Deontologistics has undergone a bit of a redesign of late. It’s needed one for a while, for various reasons. But the thing that motivated me to finally do it was the realisation that this is the nexus…

## Normal Service Will Resume Shortly

DEONTOLOGISTICS — 4/21/2021

Content Notes: Mental Health, Neurodiversity, Bipolar Disorder, Plurality/Multiplicity, TERFism, Personal Identity, Posthumanism. Length (~18K). PDF. 0. Vicious Cycles Another year, another extended absence. What a year though, right? Given how…

## Regression and Linear Combinations

Math ∩ Programming — 3/29/2021

Recently I’ve been helping out with a linear algebra course organized by Tai-Danae Bradley and Jack Hidary, and one of the questions that came up a few times was, “why should programmers care about the concept of a linear combination?” For those…

## Searching for RH Counterexamples — Productionizing

Math ∩ Programming — 3/6/2021

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Scaling up In the last article we rearchitected the…

## Lost in the Labyrinth

DEONTOLOGISTICS — 2/25/2021

Content Notes: Amateur Genetics, Neurodiversity, Nick Land, NRx, Racism, Ignorance, Stupidity, Addiction As some people may have noticed, my experiments in using twitter as a platform for philosophical writing have become a bit more interactive of…

## Searching for RH Counterexamples — Scaling Up

Math ∩ Programming — 2/16/2021

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker Performance Profiling Last time we made the audacious choice to remove primary…

## Searching for RH Counterexamples — Performance Profiling

Math ∩ Programming — 2/2/2021

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded integers Deploying with Docker In the last article we ran into some performance issues with our deployed…

## Searching for RH Counterexamples — Deploying with Docker

Math ∩ Programming — 1/4/2021

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search Strategies Unbounded Integers In this article we’ll deploy the application on a server, so that it can search for RH…

## Matrices as Tensor Network Diagrams

Math3ma — 12/29/2020

In the previous post, I described a simple way to think about matrices, namely as bipartite graphs. Today I’d like to share a different way to picture matrices—one which is used not only in mathematics, but also in physics and machine learning….

## Limits and Colimits Part 3 (Examples)

Math3ma — 12/29/2020

Once upon a time, we embarked on a mini-series about limits and colimits in category theory. Part 1 was a non-technical introduction that highlighted two ways mathematicians often make new mathematical objects from existing ones: by taking a…

## The Tensor Product, Demystified

Math3ma — 12/29/2020

Previously on the blog, we’ve discussed a recurring theme throughout mathematics: making new things from old things. Today, I’d like to focus on a particular way to build a new vector space from old vector spaces: the tensor product. This…

## What is an Adjunction? Part 1 (Motivation)

Math3ma — 12/29/2020

Some time ago, I started a blog series introducing the basics of category theory (categories, functors, natural transformations). Today, adjunctions are now on the list! So, what *is* an adjunction? Here’s the start to a leisurely stroll through…

## crumbs!

Math3ma — 12/29/2020

Recently I’ve been working on a dissertation proposal, which is sort of like a culmination of five years of graduate school (yay). The first draft was rough, but I sent it to my advisor anyway. A few days later I walked into his office, smiled, and…

## Viewing Matrices & Probability as Graphs

Math3ma — 12/29/2020

Today I’d like to share an idea. It’s a very simple idea. It’s not fancy and it’s certainly not new. In fact, I’m sure many of you have thought about it already. But if you haven’t—and even if you have!—I hope you’ll take a few minutes to enjoy it…

## A First Look at Quantum Probability, Part 1

Math3ma — 12/29/2020

In this article and the next, I’d like to share some ideas from the world of quantum probability. The word “quantum” is pretty loaded, but don’t let that scare you. We’ll take a first—not second or third—look at the subject, and the only…

## A First Look at Quantum Probability, Part 2

Math3ma — 12/29/2020

Welcome back to our mini-series on quantum probability! Last time, we motivated the series by pondering over a thought from classical probability theory, namely that marginal probability doesn’t have memory. That is, the process of summing over of…

## What is an Adjunction? Part 2 (Definition)

Math3ma — 12/29/2020

Last time I shared a light introduction to adjunctions in category theory. As we saw then, an adjunction consists of a pair of opposing functors $F$ and $G$ together with natural transformations $\text{id}\to\ GF$ and $FG\to\text{id}$ that interact…

## What is an Adjunction? Part 3 (Examples)

Math3ma — 12/29/2020

Welcome to the last installment in our mini-series on adjunctions in category theory. We motivated the discussion in Part 1 and walked through formal definitions in Part 2. Today I’ll share some examples. In Mac Lane’s well-known words, “adjoint…

## crumbs!

Math3ma — 12/29/2020

There are a couple of questions that I’m asked quite frequently these days: “How far along are you in graduate school?” “What’s your research about anyways?” I created Math3ma precisely for my time in graduate school, so I thought it’d be…

## Applied Category Theory 2020

Math3ma — 12/29/2020

Hi all, just ducking in to help spread the word: the annual applied category theory conference (ACT2020) is taking place remotely this summer! Be sure to check out the conference website for the latest updates. As you might know, I was around for…

## Topology: A Categorical Approach

Math3ma — 12/29/2020

I’ve been collaborating on an exciting project for quite some time now, and today I’m happy to share it with you. There is a new topology book on the market! Topology: A Categorical Approach is a graduate-level textbook that presents basic topology…

## At the Interface of Algebra and Statistics

Math3ma — 12/29/2020

I’m happy to share that I’ve successfully defended my PhD thesis, and my dissertation—”At the Interface of Algebra and Statistics”—is now available online at arXiv:2004.05631. In a few words, my thesis uses basic tools from quantum physics to…

## What’s Next? (An Update)

Math3ma — 12/29/2020

Before introducing today’s post, I’d like to first thank everyone who’s reached out to me about my thesis and video posted last week. Thanks! I appreciate all the generous feedback. Now onto the topic of the day: I’d like to share an update about…

## Language Modeling with Reduced Densities

Math3ma — 12/29/2020

Today I’d like to share with you a new paper on the arXiv [2007.03834]—my latest project in collaboration with mathematician Yiannis Vlassopoulos (Tunnel, IHES). In it, We present a framework for modeling words, phrases, and longer expressions in a…

## Topology Book Launch

Math3ma — 12/29/2020

This is the official launch week of our new book, “Topology: A Categorical Approach,” which is now available for purchase! We are also happy to offer a free open access version through MIT Press at topology.mitpress.mit.edu. [Read more on Math3ma!]

## Finitely Generated Modules Over a PID

Math3ma — 12/12/2020

We know what it means to have a module $M$ over a (commutative, say) ring $R$. We also know that if our ring $R$ is actually a field, our module becomes a vector space. But what happens if $R$ is “merely” a PID? Answer: A lot. Today we’ll look at a…

## Optimization Models for Subset Cover

Math ∩ Programming — 10/20/2020

In a recent newsletter article I complained about how researchers mislead about the applicability of their work. I gave SAT solvers as an example. People provided interesting examples in response, but what was new to me was the concept of SMT…

## What do Polygons and Galois Theory Have in Common?

Math3ma — 10/15/2020

Galois Theory is all about symmetry. So, perhaps not surprisingly, symmetries found among the roots of polynomials (via Galois theory) are closely related to symmetries of polygons in the plane (via geometry). In fact, the two are highly analogous!

## Searching for RH Counterexamples — Unbounded Integers

Math ∩ Programming — 10/13/2020

We’re ironically searching for counterexamples to the Riemann Hypothesis. Setting up Pytest Adding a Database Search strategies In the last article, we improved our naive search from “try all positive integers” to enumerate a subset of integers…

## Searching for RH Counterexamples — Search Strategies

Math ∩ Programming — 9/28/2020

We’re glibly searching for counterexamples to the Riemann Hypothesis, to trick you into learning about software engineering principles. In the first two articles we configured a testing framework and showed how to hide implementation choices behind…

## Searching for RH Counterexamples — Adding a Database

Math ∩ Programming — 9/11/2020

In the last article we set up pytest for a simple application that computes divisor sums $ \sigma(n)$ and tries to disprove the Riemann Hypothesis. In this post we’ll show how to extend the application as we add a database dependency. The database…

## Searching for RH Counterexamples — Setting up Pytest

Math ∩ Programming — 9/11/2020

Some mathy-programmy people tell me they want to test their code, but struggle to get set up with a testing framework. I suspect it’s due to a mix of: There are too many choices with a blank slate. Making slightly wrong choices early on causes…

## Taylor Series and Accelerometers

Math ∩ Programming — 7/26/2020

In my book, A Programmer’s Introduction to Mathematics, I describe the Taylor Series as a “hammer for every nail.” I learned about another nail in the design of modern smartphone accelerometers from “Eight Amazing Engineering Stories” by Hammack,…

## Visual Linear Logic

mathematical fantasies — 6/8/2020

What even is logic anyway? Logic is about what patterns of thought are valid. There are different kinds of logic for thinking about different kinds of things. Classical logic is for thinking about truth. Intuitionistic logic is for thinking about…

## Contextual Symbols in Math

Math ∩ Programming — 5/22/2020

In my book I discuss the importance of context in reading and writing mathematics. An early step in becoming comfortable with math is deciphering the syntax of mathematical expressions. Another is in connecting the symbols to their semantic…

## Musings on A New Interface for Mathematics

Math ∩ Programming — 5/17/2020

This essay is a slightly modified version of the closing chapter of A Programmer’s Introduction to Mathematics. We are no longer constrained by pencil and paper. The symbolic shuffle should no longer be taken for granted as the fundamental…

## Second Edition of A Programmer’s Introduction to Mathematics

Math ∩ Programming — 5/17/2020

The Second Edition of A Programmer’s Introduction to Mathematics is now available on Amazon. The second edition includes a multitude of fixes to typos and some technical errata, thanks to my readers who submitted over 200 errata. Readers who…

## The Yoneda Perspective

Math3ma — 4/21/2020

In the words of Dan Piponi, it “is the hardest trivial thing in mathematics.” The nLab catalogues it as “elementary but deep and central,” while Emily Riehl nominates it as “arguably the most important result in category theory.” Yet as Tom…

## Ways to Show a Group is Abelian

Math3ma — 2/7/2020

After some exposure to group theory, you quickly learn that when trying to prove a group $G$ is abelian, checking if $xy=yx$ for arbitrary $x,y$ in $G$ is not always the most efficient - or helpful! - tactic. Here is a (not comprehensive) running…

## What is a Natural Transformation? Definition and Examples

Math3ma — 1/30/2020

I hope you have enjoyed our little series on basic category theory. (I know I have!) This week we’ll close out by chatting about natural transformations which are, in short, a nice way of moving from one functor to another. If you’re new to this…

## The Yoneda Embedding

Math3ma — 1/29/2020

Last week we began a discussion about the Yoneda lemma. Though rather than stating the lemma (sans motivation), we took a leisurely stroll through an implication of its corollaries - the Yoneda perspective, as we called it: An object is completely…

## The Communicative Value of Using Git Well

Math ∩ Programming — 1/14/2020

Recently my employer (Google) forced me to switch to Mercurial instead of my usual version control system, git. The process of switching sparked a few discussions between me and my colleagues about the value of various version control systems. A…

## Hecke orbits and Homotopy

Good Fibrations — 1/7/2020

I thought it might be of interest to homotopy theorists to learn how the Lubin-Tate action is relevant in the Hecke orbit conjecture. Here is a beginner friendly summary. heckeorbitshomotopy

## TfE: Varieties of Rule Following

DEONTOLOGISTICS — 12/27/2019

Here’s a thread from a few weeks ago, explaining an interesting but underexplored overlap between a theoretical problem in philosophy and a practical problem in computer science: Okay, it looks like I’m going to have to explain my take on the…

## Rational Canonical Form: Example #1

Math3ma — 12/27/2019

Last time we discussed the rational canonical form (RCF) of a linear transformation, and we mentioned that any two similar linear transformations have the same RCF. It’s this fact which allows us to classify distinct linear transformations on a…

## TfE: Turing and Hegel

DEONTOLOGISTICS — 12/21/2019

Here’s a thread on something I’ve been thinking about for a few years now. I can’t say I’m the only one thinking about this convergence, but I like to think I’m exploring it from a slightly different direction. I increasingly think the Turing test…

## Compact + Hausdorff = Normal

Math3ma — 12/3/2019

The notion of a topological space being Hausdorff or normal identifies the degree to which points or sets can be “separated.” In a Hausdorff space, it’s guaranteed that if you pick any two distinct points in the space – say $x$ and $y$ – then you…

## A Good Year for “A Programmer’s Introduction to Mathematics”

Math ∩ Programming — 12/1/2019

A year ago today I self-published “A Programmer’s Introduction to Mathematics” (PIM). In this short note I want to describe the success it’s had, summarize the complaints of some readers and the praise of others, and outline what’s next. Since…

## Honda, Taira, On the Formal Structure of the Jacobian Variety of the Fermat Curve over a (p)-adic Integer Ring

Good Fibrations — 11/26/2019

This paper of Honda was very hard for me to track down. I found it in a retired library volume in a thrift store in England. It was not previously available digitally. Hopefully, this digital copy will make it easier for others to enjoy Honda’s…

## TfE: From Cyberpunk to Infopunk

DEONTOLOGISTICS — 11/25/2019

I have a somewhat tortured relationship to literary and cultural criticism. I think that, like most people, some of my most complex and nuanced opinions are essentially aesthetic. I’ve written quite a lot about the nature of art, aesthetics, and…

## TfE: Incompetence, Malice, and Evil

DEONTOLOGISTICS — 11/5/2019

Here’s a thread from Saturday that seemed to be quite popular. It explains a saying that I’ve found myself reaching for a lot recently, using some other ideas I’ve been developing in the background on the intersection between philosophy of action,…

## TfE: Information and Energy

DEONTOLOGISTICS — 11/1/2019

Here’s another bit of spontaneous Facebook philosophy, responding to a post by my friend Carl Sachs. The following thoughts are largely inspired by Samson Abramsky‘s majestic ‘Information, Processes and Games‘. So, say I’ve got a biological…

## crumbs!

Math3ma — 8/19/2019

One of my students recently said to me, “I’m not good at math because I’m really slow.” Right then and there, she had voiced what is one of many misconceptions that folks have about math. But friends, speed has nothing to do with one’s ability to…

## Silent Duels—Constructing the Solution part 1

Math ∩ Programming — 6/30/2019

Previous posts in this series: Silent Duels and an Old Paper of Restrepo Silent Duels—Parsing the Construction Last time we waded into Restrepo’s silent duel paper. You can see the original and my re-typeset version on Github along with all of the…

## Limits and Colimits, Part 2 (Definitions)

Math3ma — 6/29/2019

Welcome back to our mini-series on categorical limits and colimits! In Part 1 we gave an intuitive answer to the question, “What are limits and colimits?” As we saw then, there are two main ways that mathematicians construct new objects from a…

## Math Versus Dirty Data

Math ∩ Programming — 6/8/2019

At Google, our organization designs, owns, and maintains a number of optimization models that automate the planning of Google’s datacenter growth and health. As is pretty standard in supply chain optimization and planning, these models are often…

## Snippets of Mathematical Candor

Math3ma — 6/7/2019

A while ago I wrote a post in response to a great Slate article reminding us that math - like writing - isn’t something that anyone is good at without (at least a little!) effort. As the article’s author put it, “no one is born knowing the axiom of…

## Constructing the Tensor Product of Modules

Math3ma — 5/15/2019

Today we talk tensor products. Specifically this post covers the construction of the tensor product between two modules over a ring. But before jumping in, I think now’s a good time to ask, “What are tensor products good for?” Here’s a simple…

## The Integral Domain Hierarchy, Part 2

Math3ma — 5/15/2019

In any area of math, it’s always good idea to keep a few counterexamples in your back pocket. This post continues part 1 with examples/non-examples from some of the different subsets of integral domains.

## Sperner’s lemma

mathematical fantasies — 5/13/2019

I found a proof of Sperner’s lemma that I am quite satisfied with a few months ago. I’ll repeat the proof here, but more importantly I’d like to share my thought process that lead to the proof. What is Sperner’s lemma? Look at the triangle below….

## Commutative Diagrams Explained

Math3ma — 5/6/2019

Have you ever come across the words “commutative diagram” before? Perhaps you’ve read or heard someone utter a sentence that went something like, “For every [bla bla] there existsa [yadda yadda] such thatthe following diagram commutes.” and perhaps…

## A Working Mathematician’s Guide to Parsing

Math ∩ Programming — 4/20/2019

Our hero, a mathematician, is writing notes in LaTeX and needs to convert it to a format that her blog platform accepts. She’s used to using dollar sign delimiters for math mode, but her blog requires ( ) and [ ]. Find-and-replace fails because…

## Overview of the Classic Theory of p-Divisible groups

Good Fibrations — 4/10/2019

Here are the texed notes for my 1 hour oberwolfach talk (the key thing I left out is Cartier duality). I included Manin’s original approach, and remark on some details I find left out of most sources.

## Comparing Topologies

Math3ma — 4/5/2019

It’s possible that a set $X$ can be endowed with two or more topologies that are comparable. Over the years, mathematicians have used various words to describe the comparison: a topology $\tau_1$ is said to be coarser than another topology…

## Silent Duels—Parsing the Construction

Math ∩ Programming — 1/28/2019

Last time we discussed the setup for the silent duel problem: two players taking actions in $ [0,1]$, player 1 gets $ n$ chances to act, player 2 gets $ m$, and each knows their probability of success when they act. The solution is in a paper of…

## A Math Blog? Say What?

Math3ma — 1/24/2019

Yes! I’m writing about math. No! Don’t close your browser window. Hear me out first… I know very well that math has a bad rap. It’s often taught or thought of as a dry, intimidating, unapproachable, completely boring,…

## Limits and Colimits, Part 1 (Introduction)

Math3ma — 1/24/2019

I’d like to embark on yet another mini-series here on the blog. The topic this time? Limits and colimits in category theory! But even if you’re not familiar with category theory, I do hope you’ll keep reading. Today’s post is just an informal,…

## Announcing Applied Category Theory 2019

Math3ma — 1/9/2019

Hi everyone. Here’s a quick announcement: the Applied Category Theory 2019 school is now accepting applications! As you may know, I participated in ACT2018, had a great time, and later wrote a mini-book based on it. This year, it’s happening again…

## Notes on Applied Category Theory

Math3ma — 1/6/2019

Have you heard the buzz? Applied category theory is gaining ground! But, you ask, what is applied category theory? Upon first seeing those words, I suspect many folks might think either one of two thoughts: 1. Applied category theory? Isn’t that an…

## Silent Duels and an Old Paper of Restrepo

Math ∩ Programming — 12/31/2018

Two men start running at each other with loaded pistols, ready to shoot! It’s a foggy morning for a duel. Newton and Leibniz have decided this macabre contest is the only way to settle their dispute over who invented Calculus. Each pistol is fitted…

## Automorphisms of the Jacobian

Good Fibrations — 12/31/2018

Here, (A) is any abelian variety. This post consists of the backstory of my latest paper with Dami Lee and something interesting I learned about the relationship between the size of (Aut(A)), and the number of principal polarizations (A) has.

## Fiber Bundles of Formal Disks

Good Fibrations — 12/31/2018

Here is an incomplete proof that varieties are fiber bundles of formal disks over their deRham Stacks. The fact makes intuitive sense, the deRham stack is the variety without infinitesimal data, and then by adding the infinitesimal data (formal…

## A Programmer’s Introduction to Mathematics

Math ∩ Programming — 12/1/2018

For the last four years I’ve been working on a book for programmers who want to learn mathematics. It’s finally done, and you can buy it today. The website for the book is pimbook.org, which has purchase links—paperback and ebook—and a preview of…

## Operator Norm, Intuitively

Math3ma — 11/23/2018

If $X$ and $Y$ are normed vector spaces, a linear map $T:X\to Y$ is said to be bounded if $|T|< \infty$ where $$|T|=\sup_{\underset{x\neq 0}{x\in X}}\left{\frac{ | T(x) | }{ | x | }\right}.$$ (Note that $ | T(x) | $ is the norm in $Y$ whereas $ | x | $ is… |

## “Up to Isomorphism”?

Math3ma — 11/23/2018

Up to isomorphism” is a phrase that seems to get thrown around a lot without ever being explained. Simply put, we say two groups (or any other algebraic structures) are the same “up to isomorphism” if they’re isomorphic! In other words, they share…

## Borel-Cantelli Lemma (Pictorially)

Math3ma — 11/23/2018

The Borel-Cantelli Lemma says that if $(X,\Sigma,\mu)$ is a measure space with $\mu(X)<\infty$ and if ${E_n}*{n=1}^\infty$ is a sequence of measurable sets such that $\sum_n\mu(E_n)<\infty$, then $$\mu\left(\bigcap*{n=1}^\infty…

## English is Not Commutative

Math3ma — 11/23/2018

Here’s another unspoken rule of mathematics: English doesn’t always commute! Word order is important…

## What’s a Transitive Group Action?

Math3ma — 11/23/2018

Let a group $G$ act on a set $X$. The action is said to be transitive if for any two $x,y\in X$ there is a $g\in G$ such that $g\cdot x=y$. This is equivalent to saying there is an $x\in X$ such that $\text{orb}(x)=X$, i.e. there is exactly one…

## Need to Prove Your Ring is NOT a UFD?

Math3ma — 11/23/2018

You’re given a ring $R$ and are asked to show it’s not a UFD. Where do you begin? One standard trick is to apply the Rational Roots Theorem….

## Why are Noetherian Rings Special?

Math3ma — 11/23/2018

In short, “Noetherian-ness” is a property which generalizes “PID-ness.” As Keith Conrad so nicely puts it, “The property of all ideals being singly generated is often not preserved under common ring-theoretic constructions (e.g. $\mathbb{Z}$ is a…

## One Unspoken Rule of Algebra

Math3ma — 11/23/2018

Here’s an algebra tip! Whenever you’re asked to prove \(A/B\cong C\) where $A,B,C$ are groups, rings, fields, modules, etc., mostly likely the The First Isomorphism Theorem involved!

## Completing a Metric Space, Intuitively

Math3ma — 11/23/2018

An incomplete metric space is very much like a golf course: it has a lot of missing points!

## One Unspoken Rule of Measure Theory

Math3ma — 11/23/2018

Here’s a measure theory trick: when asked to prove that a set of points in $\mathbb{R}$ (or some measure space $X$) has a certain property, try to show that the set of points which does NOT have that property has measure 0! This technique is used…

## Learning How to Learn Math

Math3ma — 11/18/2018

Once upon a time, while in college, I decided to take my first intro-to-proofs class. I was so excited. “This is it!” I thought, “now I get to learn how to think like a mathematician.” You see, for the longest time, my mathematical upbringing was…

## Ex-Hack: a Haskell Example-based Documentation

AlternativeBit — 11/15/2018

Abstract Ex-Hack is an example-based documentation automatically generated using the packages posted on Stackage. There’s a live demo here. We’ve just released the alpha version; you can have a look to the code here. We are actively looking for new…

## 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…