Patrick Dugan

Patrick Dugan

he/him

M.S.E./B.S.E. in CS and B.A. in Math at Penn. Combinatorics, learning theory, ML systems.

Dirichlet Convolutions

1 minute read

Published:

An introduction to Dirichlet convolution, written the summer after my junior year of high school. I knew the Möbius function existed but deliberately didn’t look up its definition, so I could try to reconstruct it from what it had to do: invert the constant-one function under convolution. The write-up builds up from that.

Looking back, this is where my interest in Möbius functions started. They’re the main tool in my chain polynomial paper, which uses the Möbius function of a poset, and of graphs more generally, to locate real roots.

See it

Below is the divisor lattice of n. Each node is a divisor d, coloured by μ(d): blue for +1, red for −1, hollow for 0. The line underneath checks Σd|n μ(d) = 0 and uses Möbius inversion to recover φ(n) from n = Σd|n φ(d).

Click a divisor d to highlight the interval [d, n]. The widget then computes the Möbius function of that interval as a poset, from its recursion alone, and it always comes out to μ(n/d). That’s the bridge from this post to my paper: the Möbius function of a poset generalizes this one, and its signs are what the paper uses to locate roots.

Read the write-up (PDF)

You May Also Enjoy

Complex Image Mapping

1 minute read

Published:

In this blog post I will be talking about a piece of software I made for my final project in my Senior year highschool art class.

Fields

less than 1 minute read

Published:

This is part 3 of a three-part series, written in my junior year of high school, that works up to proving that (Z/pZ)× is cyclic: the multiplicative group of integers mod a prime has a generator. I was teaching myself group theory at the time and worked out the route on my own, so the proofs are mine rather than the textbook’s.

Factoring Polynomials in Arbitrary Fields

less than 1 minute read

Published:

This is part 2 of a three-part series, written in my junior year of high school, that works up to proving that (Z/pZ)× is cyclic: the multiplicative group of integers mod a prime has a generator. I was teaching myself group theory at the time and worked out the route on my own, so the proofs are mine rather than the textbook’s.

Some Results with Kernels

less than 1 minute read

Published:

This is part 1 of a three-part series, written in my junior year of high school, that works up to proving that (Z/pZ)× is cyclic: the multiplicative group of integers mod a prime has a generator. I was teaching myself group theory at the time and worked out the route on my own, so the proofs are mine rather than the textbook’s.