Group Theory: Lagrange’s Theorem and the Sudoku Principle

Voltaire said to not let the perfect be the enemy of the good. In that spirit, I’ve decided to post a few (highly imperfect) video lectures I recently on group theory. There’s a lot of things I would do to go back and improve these lectures, but I hope that the content makes up for any flaws!

There will be a third one coming soon, and will be a working-through of an example that shows the power of Lagrange’s theorem. This format is a bit of an experiment for me, and I’ll keep working to make it better. I hope you enjoy!

The Most Irrational of Numbers

Today I have a new interactive demonstration for you!

Controls
Zoom in: W
Zoom out: S
Reset angle: 0
Switch mode (auto or user): Space
On “User Mode”:
– Increase angle: Up
– Decrease angle: Down

(As always, zooming out too much will make things begin to lag. Also, fair warning, things start getting a little seizure-inducing around a zoom of .5 or less.)

Okay! Pretty, right? But what’s actually going on?

Each frame we are drawing a sequence of dots. We start at the center of the screen, and take constant radial steps outwards. And for each step, we apply some fixed angular rotation. This angular rotation is given as a percentage of 2π on the top of the screen, and is the thing being adjusted frame by frame (either automatically or based on your input, depending on which mode you choose).

What’s cool is what happens when you approach simple rational numbers. Take a look for yourself by going on “User” mode and bringing the angle to 10% (for 1/10), 14.28% (for 1/7), 25% (for 1/4), and so on. Here are two examples:

Screen Shot 2019-07-09 at 11.27.02 PMScreen Shot 2019-07-09 at 11.27.28 PM

Cool, right? At every rational number, we end up with a number of “spokes” corresponding to the denominator of our rational number. People sometimes describe the golden ratio Ф as the “most irrational number”, meaning that in some sense it is the most difficult to approximate by rational numbers. How does this look on our visualization? Check it out!

Screen Shot 2019-07-09 at 11.32.34 PM

And zooming out further, we see…

Screen Shot 2019-07-09 at 11.33.17 PM

We can see that using Ф as our angular rotation gives us the “least spokey” shape possible. As we zoom out further and further, we will always see our points looking basically evenly distributed across the angles at any given radius. This is a wonderfully visual way to understand the irrationality of Ф!

All About Adultery, BDSM, and Divorce

I recently came across a whole bunch of crazy historical trivia, involving the laws around adultery, BDSM, and divorce. Here are some of the quotes that made me gasp (mostly from Wikipedia):

On Adultery

As of 2019, adultery remains a criminal offense in 19 states, but prosecutions are rare. Although adultery laws are mostly found in the conservative states (especially Southern states), there are some notable exceptions such as New York, Idaho, Oklahoma, Michigan, and Wisconsin consider adultery a felony, while in the other states it is a misdemeanor.

Penalties vary from a $10 fine (Maryland) to four years in prison (Michigan). In South Carolina, the fine for adultery is up to $500 and/or imprisonment for no more than one year (South Carolina code 16-15-60), and South Carolina divorce laws deny alimony to the adulterous spouse.

In Florida adultery (“Living in open adultery”, Art 798.01) is illegal; while cohabitation of unmarried couples was decriminalized in 2016.

Under South Carolina law adultery involves either “the living together and carnal intercourse with each other” or, if those involved do not live together “habitual carnal intercourse with each other” which is more difficult to prove.

In Alabama “A person commits adultery when he engages in sexual intercourse with another person who is not his spouse and lives in cohabitation with that other person when he or that other person is married.”

In some Native American cultures, severe penalties could be imposed on an adulterous wife by her husband. In many instances she was made to endure a bodily mutilation which would, in the mind of the aggrieved husband, prevent her from ever being a temptation to other men again. Among the Aztecs, wives caught in adultery were occasionally impaled, although the more usual punishment was to be stoned to death.

The Code of Hammurabi, a well-preserved Babylonian law code of ancient Mesopotamia, dating back to about 1772 BC, provided drowning as punishment for adultery.

Amputation of the nose – rhinotomy – was a punishment for adultery among many civilizations, including ancient India, ancient Egypt, among Greeks and Romans, and in Byzantium and among the Arabs.

In England and its successor states, it has been high treason to engage in adultery with the King’s wife, his eldest son’s wife and his eldest unmarried daughter. The jurist Sir William Blackstone writes that “the plain intention of this law is to guard the Blood Royal from any suspicion of bastardy, whereby the succession to the Crown might be rendered dubious.”

Adultery was a serious issue when it came to succession to the crown. Philip IV of France had all three of his daughters-in-law imprisoned, two (Margaret of Burgundy and Blanche of Burgundy) on the grounds of adultery and the third (Joan of Burgundy) for being aware of their adulterous behaviour. The two brothers accused of being lovers of the king’s daughters-in-law were executed immediately after being arrested.

Until 2018, in Indian law, adultery was defined as sex between a man and a woman without the consent of the woman’s husband. The man was prosecutable and could be sentenced for up to five years (even if he himself was unmarried) whereas the married woman cannot be jailed.

In Southwest Asia, adultery has attracted severe sanctions, including death penalty. In some places, such as Saudi Arabia, the method of punishment for adultery is stoning to death. Proving adultery under Muslim law can be a very difficult task as it requires the accuser to produce four eyewitnesses to the act of sexual intercourse, each of whom should have a good reputation for truthfulness and honesty. The criminal standards do not apply in the application of social and family consequences of adultery, where the standards of proof are not as exacting.

Adultery is no longer a crime in any European country. Among the last Western European countries to repeal their laws were Italy (1969), Malta (1973), Luxembourg (1974), France (1975), Spain (1978), Portugal (1982), Greece (1983), Belgium (1987), Switzerland (1989), and Austria (1997).

In most Communist countries adultery was not a crime. Romania was an exception, where adultery was a crime until 2006, though the crime of adultery had a narrow definition, excluding situations where the other spouse encouraged the act or when the act happened at a time the couple was living separate and apart; and in practice prosecutions were extremely rare.

English common law defined the crime of seduction as a felony committed “when a male person induced an unmarried female of previously chaste character to engage in an act of sexual intercourse on a promise of marriage.” A father had the right to maintain an action for the seduction of his daughter (or the enticement of a son who left home), since this deprived him of services or earnings.

In more modern times, Frank Sinatra was charged in New Jersey in 1938 with seduction, having enticed a woman “of good repute to engage in sexual intercourse with him upon his promise of marriage. The charges were dropped when it was discovered that the woman was already married.”

Buddhist Pali texts narrate legends where the Buddha explains the karmic consequences of adultery. For example, states Robert Goldman, one such story is of Thera Soreyya. Buddha states in the Soreyya story that “men who commit adultery suffer hell for hundreds of thousands of years after rebirth, then are reborn a hundred successive times as women on earth, must earn merit by “utter devotion to their husbands” in these lives, before they can be reborn again as men to pursue a monastic life and liberation from samsara.

According to Muhammad, an unmarried person who commits adultery or fornication is punished by flogging 100 times; a married person will then be stoned to death. A survey conducted by the Pew Research Center found support for stoning as a punishment for adultery mostly in Arab countries; it was supported in Egypt (82% of respondents in favor of the punishment) and Jordan (70% in favor), as well as Pakistan (82% favor), whereas in Nigeria (56% in favor) and in Indonesia (42% in favor) opinion is more divided, perhaps due to diverging traditions and differing interpretations of Sharia.

The Roman Lex Julia, Lex Iulia de Adulteriis Coercendis (17 BC), punished adultery with banishment. The two guilty parties were sent to different islands (“dummodo in diversas insulas relegentur”), and part of their property was confiscated. Fathers were permitted to kill daughters and their partners in adultery. Husbands could kill the partners under certain circumstances and were required to divorce adulterous wives.

Durex’s Global Sex Survey found that worldwide 22% of people surveyed admitted to have had extramarital sex. In the United States Alfred Kinsey found in his studies that 50% of males and 26% of females had extramarital sex at least once during their lifetime. Depending on studies, it was estimated that 26–50% of men and 21–38% of women, or 22.7% of men and 11.6% of women, had extramarital sex. Other authors say that between 20% and 25% of Americans had sex with someone other than their spouse. Three 1990s studies in the United States, using nationally representative samples, have found that about 10–15% of women and 20–25% of men admitted to having engaged in extramarital sex.

The Standard Cross-Cultural Sample described the occurrence of extramarital sex by gender in over 50 pre-industrial cultures. The occurrence of extramarital sex by men is described as “universal” in 6 cultures, “moderate” in 29 cultures, “occasional” in 6 cultures, and “uncommon” in 10 cultures. The occurrence of extramarital sex by women is described as “universal” in 6 cultures, “moderate” in 23 cultures, “occasional” in 9 cultures, and “uncommon” in 15 cultures.

Traditionally, many cultures, particularly Latin American ones, had strong double standards regarding male and female adultery, with the latter being seen as a much more serious violation.

Adultery involving a married woman and a man other than her husband was considered a very serious crime. In 1707, English Lord Chief Justice John Holt stated that a man having sexual relations with another man’s wife was “the highest invasion of property” and claimed, in regard to the aggrieved husband, that “a man cannot receive a higher provocation” (in a case of murder or manslaughter).

The Encyclopedia of Diderot & d’Alembert, Vol. 1 (1751), also equated adultery to theft writing that, “adultery is, after homicide, the most punishable of all crimes, because it is the most cruel of all thefts, and an outrage capable of inciting murders and the most deplorable excesses.”

On BDSM

The United States Federal law does not list a specific criminal determination for consensual BDSM acts. Some states specifically address the idea of “consent to BDSM acts” within their assault laws, such as the state of New Jersey, which defines “simple assault” to be “a disorderly persons offense unless committed in a fight or scuffle entered into by mutual consent, in which case it is a petty disorderly persons offense”.

Mutual combat, a term commonly used in United States courts, occurs when two individuals intentionally and consensually engage in a fair fight, while not hurting bystanders or damaging property. There is not an official law that forbids mutual combat in the United States. There have been numerous cases where this concept was successfully used in defense of the accused. In some cases, mutual combat may nevertheless result in killings.

Oregon Ballot Measure 9 was a ballot measure in the U.S. state of Oregon in 1992, concerning sadism, masochism, gay rights, pedophilia, and public education, that drew widespread national attention. It would have added the following text to the Oregon Constitution:

All governments in Oregon may not use their monies or properties to promote, encourage or facilitate homosexuality, pedophilia, sadism or masochism. All levels of government, including public education systems, must assist in setting a standard for Oregon’s youth which recognizes that these behaviors are abnormal, wrong, unnatural and perverse and they are to be discouraged and avoided.

Dildos or any object used for “the stimulation of human genital organs” cannot be made or sold in Alabama. The Anti-Obscenity Enforcement Act says that anyone caught with such tools could face a fine up to $20,000, a one-year jail sentence or 12-months doing hard labor.

Florida bans “lewd and lascivious behavior,” which is defined as a situation where “any man and woman, not being married to each other, lewdly and lasciviously associate and cohabit together.” The misdemeanor is punishable by a fine of up to $500. In Mississippi, an unmarried couple caught living together “whether in adultery or fornication” can face up to six months in jail and/or a $500 fine.

In 2003, the U.S. Supreme Court deemed a Texas state law that banned the practice of anal and oral sex between same-sex couples as unconstitutional. Despite the ruling, a sizable list of states, including Texas, still have anti-sodomy laws on the books.

Louisiana’s “crime against nature” statute prohibits the “the unnatural carnal copulation by a human being with another of the same sex or opposite sex or with an animal.” The state legislature in April failed to pass a bill that would have repealed the law except for human-on-animal relations.

Other states that have some form of anti-sodomy laws include Kansas, Oklahoma, Alabama, Florida, Idaho, Louisiana, Mississippi, North Carolina, South Carolina, and Utah, according to the Human Rights Campaign. Virginia repealed its ban in March.

On Divorce

Today, every state plus the District of Columbia permits no-fault divorce, though requirements for obtaining a no-fault divorce vary. California was the first U.S. state to pass a no-fault divorce law. Its law was signed by Governor Ronald Reagan, a divorced and remarried former movie actor, and came into effect in 1970. New York was the last state to pass a no-fault divorce law; that law was passed in 2010.

Prior to the advent of no-fault divorce, a divorce was processed through the adversarial system as a civil action, meaning that a divorce could be obtained only through a showing of fault of one (and only one) of the parties in a marriage. This required that one spouse plead that the other had committed adultery, abandonment, felony, or other similarly culpable acts. However, the other spouse could plead a variety of defenses, like recrimination (essentially an accusation of “so did you”). A judge could find that the respondent had not committed the alleged act or the judge could accept the defense of recrimination and find both spouses at fault for the dysfunctional nature of their marriage. Either of these two findings was sufficient to defeat an action for divorce, which meant that the parties remained married.

Before no-fault divorce was available, spouses seeking divorce would often allege false grounds for divorce. Removing the incentive to perjure was one motivation for the no-fault movement.

In the States of Wisconsin, Oregon, Washington, Nevada, Nebraska, Montana, Missouri, Minnesota, Michigan, Kentucky, Kansas, Iowa, Indiana, Hawaii, Florida, Colorado and California, a person seeking a divorce is not permitted to allege a fault-based ground (e.g. adultery, abandonment or cruelty).

In some states, requirements were even more stringent. For instance, under its original (1819) constitution, Alabama required not only the consent of a court of chancery for a divorce (and only “in cases provided for by law”), but equally that of two-thirds of both houses of the state legislature. This requirement was dropped in 1861, when the state adopted a new constitution at the outset of the American Civil War. The required vote in this case was even stricter than that required to overturn the governor’s veto in Alabama, which required only a simple majority of both houses of the General Assembly.

These requirements could be problematic if both spouses were at fault or if neither spouse had committed a legally culpable act but both spouses desired a divorce by mutual consent. Lawyers began to advise their clients on how to create legal fictions to bypass the statutory requirements. One method popular in New York was referred to as “collusive adultery”, in which both sides deliberately agreed that the wife would come home at a certain time and discover her husband committing adultery with a “mistress” obtained for the occasion. The wife would then falsely swear to a carefully tailored version of these facts in court (thereby committing perjury). The husband would admit a similar version of those facts. The judge would convict the husband of adultery, and the couple could be divorced. Specifically, they report that “states that adopted no-fault divorce experienced a decrease of 8 to 16 percent in wives’ suicide rates and a 30 percent decline in domestic violence.”

The Code of Hammurabi (1754 BC) declares that a man must provide sustenance to a woman who has borne him children, so that she can raise them:

If a man wish to separate from a woman who has borne him children, or from his wife who has borne him children: then he shall give that wife her dowry, and a part of the usufruct of field, garden, and property, so that she can rear her children. When she has brought up her children, a portion of all that is given to the children, equal as that of one son, shall be given to her. She may then marry the man of her heart.

In the 1970s, the United States Supreme Court ruled against gender bias in alimony awards and, according to the U.S. Census Bureau, the percentage of alimony recipients who are male rose from 2.4% in 2001 to 3.6% in 2006. In states like Massachusetts and Louisiana, the salaries of new spouses may be used in determining the alimony paid to the previous partners.

Some of the possible factors that bear on the amount and duration of the support are:

Factor

Description

Length of the marriage or civil union

Generally, alimony lasts for a term or period. However, it will last longer if the marriage or civil union lasted longer. A marriage or civil union of over 10 years is often a candidate for permanent alimony.

Time separated while still married

In some U.S. states, separation is a triggering event, recognized as the end of the term of the marriage. Other U.S. states do not recognize separation or legal separation. In a state not recognizing separation, a 2-year marriage followed by an 8-year separation will generally be treated like a 10-year marriage.

Age of the parties at the time of the divorce

Generally, more youthful spouses are considered to be more able to ‘get on’ with their lives, and therefore thought to require shorter periods of support.

Relative income of the parties

In U.S. states that recognize a right of the spouses to live ‘according to the means to which they have become accustomed’, alimony attempts to adjust the incomes of the spouses so that they are able to approximate, as best possible, their prior lifestyle.

Future financial prospects of the parties

A spouse who is going to realize significant income in the future is likely to have to pay higher alimony than one who is not.

Health of the parties

Poor health goes towards need, and potentially an inability to support oneself. The courts are disinclined to leave one party indigent.

Fault in marital breakdown

In U.S. states where fault is recognized, fault can significantly affect alimony, increasing, reducing or even nullifying it. Many U.S. states are ‘no-fault‘ states, where one does not have to show fault to get divorced. No-fault divorce spares the spouses the acrimony of the ‘fault’ processes, and closes the eyes of the court to any and all improper spousal behavior. In Georgia, however, a person who has an affair that causes the divorce is not entitled to alimony.

Collatz Tree

For some reason, I have a fascination with all the different sequences of numbers that arise out of thinking about the Collatz conjecture. In this post, we’ll look at a few more of these.

The Collatz chain for a number N is the sequence of numbers that arise from repeatedly iterating the function
Screen Shot 2019-06-16 at 11.09.39 PM
until you get to 1. The Collatz conjecture is the statement that this sequence always terminates, no matter what n you start at.

In other words, f(N) is the function that tells you what N becomes after a single iteration. Let’s look at the inverse of this: what numbers become N after a single iteration?

One such number is 2N: 2N is always even, so after one step it falls down to n. Another possibility is m = (N-1)/3. Why? Well, if m is an odd number, then it will become 3m+1 = 3 (N-1)/3 + 1 = N – 1 + 1 = N. So for each N, we get either one or two new values.

The Collatz tree is what we get if we start at 1 and repeatedly iterate the inverse function. After n iterations, we get to the set of all numbers that take at most n steps to get to 1. Here’s what it looks like!

Screen Shot 2019-06-17 at 6.18.05 PM

I’ve never actually seen it plotted this way, and I think it shows something potentially important. Look at the order in the image! Why do we get this grid of apparently identical rhombuses? I’d love an explanation for this.

I also like the idea of “surfing” the jagged lower end of this graph, staying as small as possible while iterating f. In general, the lower end of the graph is the sequence of smallest numbers that take N steps to get to 1.

Here are the first thirty numbers in this sequence:

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 72, 25, 49, 98, 33, 65, 130, 43

Plotted, this sequence looks like:

Collatz Minimums

The first twelve of these numbers themselves form a Collatz chain. We leave this particular chain on the thirteenth step, at which point we enter a new chain containing 17. We stay in this new chain until seven steps later, at which point we enter a new chain containing 25. But now we only stay in this new chain for one step before departing for a new one! This is another sequence of numbers that fascinate me: the chain lengths at which our minimum values switch to entirely new chains. Here are the values for up to 100 steps:

12, 23, 24, 26, 27, 34, 36, 37, 38, 39, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 60, 61, 63, 64, 65, 72, 73, 74, 75, 76, 97, 98

The differences between these values are plotted here:

Differences

Whenever this plot spikes, this points to an existence of a Collatz chain that surfs the bottom of the Collatz tree for some time before jumping up to a higher value!

Record-breaking Collatz chains!

One of my favorite bits of mathematics is the Collatz conjecture. It’s so simple that you can explain it to any grade schooler, and yet is so mysterious that Paul Erdös declared “Mathematics may not be ready for such problems.”

Here’s the conjecture:

Take any natural number N. If this number is even, divide it by two. If on the other hand N is odd, we multiply it by three and add 1. So N becomes N/2 if N is even, and 3N+1 if N is odd. Now, repeat this process for the resulting number! If even, divide by two. If odd, multiply by three and add one. And then repeat with the new number, and keep on chugging away.

The conjecture is that you will always eventually get to 1 (regardless of the initial value of N!)

That’s it! It’s that simple. Here are some examples:

Say we start with N=2. Since 2 is even, we divide by 2 and get 1. And that’s that, we’re done!

What if we start with N=3? Now, since 3 is even, we must multiply by three and add 1. So 3 becomes 10. 10 is even, so we divide by 2 to get 5. And 5 is odd, so we multiply by three and add one to get 16. And lo and behold, 16 goes to 8, which goes to 4, which goes to 2, and then back down to 1!

Here’s a table of the first few “Collatz sequences”:

Screen Shot 2019-06-11 at 10.37.52 PM.png

A few comments:

First, if you look closely, you’ll notice that there’s a lot of repetition in that list. For instance, look at the chain that starts at 9. It ends up at 7 after just three steps. And then the whole rest of the chain is identical to the one two above it! And starting at 10, one step takes us to 5, the chain of which we had already calculated.

This hints that any method for calculating the Collatz sequences of numbers could likely benefit from dynamic programming: using the work you’ve previously done to make your future tasks quicker. Think about it, by calculating the chains of just the numbers 3 through 10, we’ve also managed in the process to figure out the exact chains for 11, 13, 14, 16, 17, 20, and more numbers up to 52!

Second comment: Notice that these chains look really weird. They jump up and down unpredictably, and their lengths are all over the place. Here’s what the “9” chain looks like as it jumps up and down:

Screen Shot 2019-06-11 at 10.46.17 PM.png

And, to take an even more dramatic example, here’s what the chain starting with 27 looks like:

Figure_1.png

That takes 111 steps to stop! And in the process, it rises as high as 9,232!

Based on this example, you might be thinking that these chains are in general going to increase faster than their starting value. But don’t be deceived: I cherry-picked 27 because I knew that it would generate an interesting long chain. In fact, the lengths of the chains are in general remarkably small relative to their starting value. Here’s a plot of the first 100 chain lengths:

Figure_2.png

Though the values are growing, and some of them are up in the 100s, most of them are in the sub-40 range.

If you’re like me, though, you might notice some very curious patterns in this graph. What’s going on with those clusters of three or two that keep showing up right beside each other? And why do we seem to have these two distinct “regions” of chain lengths? Let’s look to see if these patterns persist as we plot the chain lengths for higher values, this time up to 1000:

Figure_3

Interesting! So it appears like the “two regions” kind of blend together, but this pattern of strings of nearby numbers with similar chain lengths stays the same! This is extremely mysterious to me. Many of the time the specific paths the numbers take on their way to zero are quite different, so why should we see them having the same length?

Well, part of the answer might be that in fact, the paths taken by nearby numbers are sometimes actually not too different at all. For instance, 500 and 501 both take 110 steps to get to 1, but their chains become identical after just four steps. Let’s look closely at these steps:

500 becomes 250 becomes 125 becomes 376
501 becomes 1504 becomes 752 becomes 376

Let’s look in general at what happens to N and N+1 if they follow this exact sequence of moves:

N becomes N/2 becomes N/4 becomes 3N/4 + 1
N+1 becomes 3(N+1) + 1 becomes (3(N+1) + 1)/2 becomes (3(N+1) + 1)/4

But hold on: (3(N+1) + 1)/4 just is 3N/4 + 1! So in fact, we should expect that whenever we do these sequences of moves, N and N+1 will have the same chain length. And when does this happens? Well, N had to be divisible by 4 but not 8. And 3N + 4 had to be divisible by 4. This specific set of conditions is true for about 1/8 of all numbers, so this already tells us that at least 1/8 of neighboring numbers have the same length!

And this was only looking at chains that became identical after three steps! We could go further and look at other possible sequences of moves that would make our chains become identical quickly, and in the process get a better understanding of the structure of the graph.

By the way, want to see how this graph behaves for even larger starting values? Here ya go! N up to 10,000:

Figure_4

Our N has 10-tupled, but our chain lengths have barely increased at all! Same for N up to 100,000:

Figure_5

Same story! Increasing our N by a factor of 10 seems to really only increase our chain lengths by adding about 100! This indicates that the relationship between starting value and chain length might be logarithmic (a multiplicative increase in starting value corresponding to an additive increase in chain length). Let’s look at a semilog plot of the same range of starting values:

Figure_6.png

Wow! This exposes a whole new level of structure in the chain lengths. Look at all those parallel lines of clusters! And also look at how nicely linearly the chain lengths appear to grow with the exponent of the x-axis! This is a bit mind-blowing to me that the chain length of N seems to be so naturally related to log(N).

Extending this graph to 100 times more values of N:

Figure_7

We can really clearly see how linear everything remains! Another feature that pops out here is the little “ledges” that occasionally jut out to the left in the graph. These tend to appear whenever we find an N whose chain length is dramatically larger than the previous numbers, and it then carries along some of its larger neighbors.

This might raise the question: how often do we actually see new record chain lengths? I mean, clearly we’re going to get larger and larger chain lengths forever, off to infinity, but how often do these record-breaking chains appear?

Surprisingly rarely! Let’s define a record-breaking Collatz chain as a Collatz chain such that all the Collatz chains with smaller starting values are shorter in length. Let’s look at where these record-breakers appear for N up to 100,000:

Figure_9

They look pretty evenly spaced! But remember, the x-axis is growing exponentially. So in fact, they get exponentially farther apart.

By the way, look at that weird straight line that appears about midway between 101 and 102. The exact values of these record breakers are:

54: 112
73: 115
97: 118
129: 121
171: 124
241: 127
313: 130

That’s right, the record increases by exactly 3, six times in a row! This might be a fluke, or maybe there’s something deeper going on.

Also, I’m sure you’re curious about that one record-breaker that jumps way above the previous record-breakers. It turns out that you’ve already seen it: it’s 27!

27 is unique in just how much it exceeds all the previous records, going from 23 to 111 (increasing the record by 89). As you can see in the graph, no other record-breaker beats its previous records by nearly as much, even though we’re looking all the way up to 100,000. Perhaps this is just a fluke caused by the early records being especially low? This seems supported by the fact that if we look all the way up to 10 million, we still see that nothing beats 27.

Figure_9-1.png

Define a record-breaking record-breaker as a record-breaker that beats the previous record by a greater amount than all previous record breakers. Now, 27 is clearly a record-breaking record-breaker. There is also one before it, namely 3, which beats the previous record by 6. (7 is a record-tying record-breaker, as it also beats the previous record by 6.)

We might have a postulate in mind: 3 and 27 are the only record-breaking record-breakers. Can we prove this?

Well, it turns out that we can’t. Because the postulate is not true! Let’s extend our graph by another factor of 10, going up to 100 million. (By the way, the dynamic programming I mentioned earlier is absolutely essential at this point for any of this to be possible.)

Figure_10.png

Now we can see that in fact there is another record-breaking record-breaker, all the way over to the right side of the graph! It turns out to be 63,728,127, and it beats the previous record by 205! So 27 is apparently not the largest one. A new question that naturally arises, a question to which I have no answer, is: are there infinitely many record-breaking record-breakers? Or does the sequence end at some point? I conjecture that yes, there are infinitely many such overachievers.

I have two more things to geek out about before I finish up. First of all, take a look at the actual values of the record-breakers up to 10000:

2: 1
3: 7
6: 8
7: 16
9: 19
18: 20
25: 23
27: 111
54: 112
73: 115
97: 118
129: 121
171: 124
231: 127
313: 130
327: 143
649: 144
703: 170
871: 1780
1161: 181
2223: 182
2463: 208
2919: 216
3711: 237
6171: 261
10971: 267
13255: 275
17647: 278
23529: 281
26623: 307
34239: 310
35655: 323
52527: 339
77031: 350

If you skim this list over, you’ll notice that these record-breakers appear to all be odd. But there are in fact four exceptions in this list that appear near its beginning: 2, 6, 18, and 54. And after these four, the even record-breakers appear to disappear. This sort of makes sense; if the first thing you do with your number is make it larger, this will in general result in a longer chain. But are there any more even record breakers larger than 54?

As it turns out, yes there are! But the next even record breaker doesn’t appear until we get into the tens of millions. It is 31,466,382. This is pretty baffling! Try showing your friends the sequence [2, 6, 18, 54, 31466382] and see if they can figure out what comes next! (It turns out that the next number is 127,456,254, which is exactly twice the previous record breaker!)

And now one final observation. There seem to be disproportionately many record-breakers whose chain lengths differ by only 1 or 3. For the heck of it, let’s define shiftless record-breakers as any record breakers who only beat the previous record by 3, and lazy record-breakers as any record-breakers who beat the previous record by 1.

One simple way this might happen is if the previous record breaker is N, and there are no new record breakers up to 2N. Then 2N will be the new record breaker, since its first step will be dividing by 2, and then it will take the rest of Ns chain for itself. So its chain length will be one larger than the chain length of N. (By the way, it turns out that our large even record breaker is in fact an example of a lazy record breaker.)

Are there really disproportionately many lazy and shiftless record breakers? Let’s look at the amount that each record breaker beat its previous record breaker by. This sequence looks like:

6, 1, 8, 3, 1, 3, 88, 1, 3, 3, 3, 3, 3, 3, 13, 1, 26, 8, 3, 1, 26, 8, 21, 24, 6, 8, 3, 3, 26, 3, 13, 16, 11, 3, 21, 8, 3, 57, 6, 21, 39, 16, 3, 3, 26, 3, 3, 21, 13, 16, 52, 21, 3, 3, 13, 1, 39, 205

This is another really mind-blowing observation for me! It looks like the differences between record breakers always seem to take on only very specific values, like 1, 3, 6, 8, and 11. Is there ever a difference of 2? or 5? I have no idea, and I’d love to know! I’ve leave you with this histogram showing how often each difference appears in all record-breakers up to 100 million:

Figure_11

Producing all numbers using just four fours

How many of the natural numbers do you think you can produce just by combining four 4s with standard mathematical operations?

The answer might blow your mind a little bit. It’s all of them!

In particular, you can get any natural number by using the symbols ‘4’, ‘√’, ‘log’, and ‘/’. And in particular, you can do it with just four 4s!

Try it for yourself before moving on!

 

 

Continue reading “Producing all numbers using just four fours”

Buddhabrot, Mandelbrot’s older sibling

Many people have heard of Mandelbrot’s famous set. But far fewer have heard of its older sibling: the Buddhabrot. I find this object even more beautiful than the Mandelbrot set, and want to give it its proper appreciation here.

To start out with: What is the Mandelbrot set? It is defined as the set of complex values c that stay finite under arbitrary many repeated applications of the function fc(z) = z2 + c (where the first iteration is applied to z = 0).

So, for example, to check if the number 2 is in the Mandelbrot set, we just look at what happens when we plug in 0 to the function f2 and repeat:

0 becomes 02 + 2 = 2
2 becomes 22 + 2 = 6
6 becomes 62 + 2 = 38
38 becomes 382 + 2 = something large, and on and on.

You can probably predict that as we keep iterating, we’re going to eventually run off to infinity. So 2 is not in the set.

On the other hand, see what happens when we plug in -1:

0 becomes 02 + (-1) = -1
-1 becomes (-1)2 + (-1) = 0
0 becomes -1
-1 becomes 0
… and so on to infinity

With -1, we just bounce around back and forth between 0 and -1, so we clearly never diverge to infinity.

Now we can draw the elements of this set pretty easily, by simply shading in the numbers on the complex plane that are in the set. If you do so, you get the following visualization:

overallmandelbrot

Cool! But what about all those colorful visualizations you’ve probably seen? (maybe even on this blog!)

Well, whether you’re in the Mandelbrot set or not is just a binary property. So by itself the Mandelbrot set doesn’t have a rich enough structure to account for all those pretty colors. What’s being visualized in those pictures is not just whether an element is in the Mandelbrot set, but also, if it’s not in the set (i.e. if the 0 diverges to infinity upon repeated applications of fc), how quickly it leaves the set!

In other words, the colors are a representation of how not in the set numbers are. There are some complex numbers that exist near the edge of the Mandelbrot that hang around the set for many many iterations before finally blowing up and running off to infinity. And these numbers will be colored differently from, say, the number “2”, which right away starts blowing up.

And that’s how you end up with pictures like the following:

Screen Shot 2019-05-22 at 3.37.11 PM.png

Now, what if instead of visualizing how in the set various complex numbers are, we instead look at what complex numbers are most visited on average when running through Mandelbrot iterations? Well, that’s how we get the Buddhabrot!

Specifically, here’s a procedure we could run:

  1. Choose a random complex number c.
  2. Define z = 0
  3. Update: z = fc(z)
  4. Give one unit of credit to whatever complex number z is now.
  5. Repeat 3 and 4 for some fixed number of iterations.
  6. Start over back at 1 with a new complex number.

As you run this algorithm, you can visualize the results by giving complex numbers with more credits brighter colors. And as you do this, a curious figure begins to appear on the (rotated) complex plane:

Screen Shot 2019-05-22 at 4.23.06 PM.png

 

 

That’s right, Buddha is hanging out on the complex plane, hiding in the structure of the Mandelbrot set!

Hopping Midpoints

Put down three points on a piece of paper. Choose one of them as your “starting point”. Now, randomly choose one of the three points and hop from your starting point, halfway over to the chosen point. Mark down where you’ve landed. Then repeat: randomly choose one of the three starting points, and move halfway from your newly marked point to this new chosen point. Mark where you land. And on, and on, to infinity.

What pattern will arise? Watch and see!

Controls:
E to increase points/second.
Q to decrease points/second.
Click and drag the red points to move them around.
Pressing a number key will make a polygon with that number of sides.

Exploring Julia Sets

Here’s a natural follow-up to my last post on the Mandelbrot set – an interactive Julia set explorer!

The Julia set corresponding to a particular point c = x + iy in the complex plane is defined as the set of complex numbers z that stay finite upon arbitrary iterations of the following function: fc(z) = z2 + c. The Mandelbrot set, by comparison, is defined as the set of complex numbers c such that the value obtained by starting with 0 and iterating the function fc arbitrarily many times converges.

What’s remarkable is now beautiful and complex the patterns that arise from this simple equation are. Take a look for yourself: just hover over a point to see its corresponding Julia set!


Resolution is preset at a value good for seeing lots of details and loading at a reasonable speed, but should you want to change it, controls are ‘E’ to increase it and ‘Q’ to decrease it. To reset to default, press ‘SPACE’.