When Math Gets Impossibly Hard
quantamagazine.org
quantamagazine.org
I always thought that that way of thinking was pretty neat. Can the same abstraction have a different physical manifestation that's cheap to create? If you kinda squint a bit, it's what we do with computers.
The basic idea of an analog computer is you use op amps to sum voltages. Integration is easy, by adding a capacitor. By hooking up op amps, capacitors, and resistors (usually with a plugboard), you can quickly and easily solve differential equations. (Surprisingly, multiplication by a non-constant value is hard with an analog computer.)
The nice thing about analog computers is they gave the answer almost instantaneously. You could turn the dials and experiment with different parameters interactively. A digital computer in 1970, on the other hand, might take minutes to solve the same equation. This also made analog computers useful for real-time applications such as flight simulators.
A big problem with analog computers is that the accuracy is limited by your components. If you want 0.1% accuracy, you need expensive 0.1% resistors and capacitors. With a digital computer, you can get as many bits of accuracy as you want using cheap components. Basically, Moore's law killed off analog computers.
That being said, that exam was substantially shorter and easier than the Cal II exam I had to take!
Researching this topic also qualifies you to write technobabble for sci-fi movies. Like "operational trans impedance amplifier."
It's simply criminal how underutilised the technique of Automatic Differentiation is! It can solve incredibly complex differentials to machine precision, good numerical stability, and minimal tuning or hand-holding.
Lots of these "difficult" problems aren't, it's just that people aren't aware of the solution because it's not commonly taught in a University setting. Automatic Differentiation is one of those techniques that's "boring" and "numerical", so there are no courses that teach it.
An awful lot of tertiary education has been caught up in the publish-or-perish mentality. Unfortunately for AD, it is not "impressive". Differentiating hideously difficult expressions symbolically is impressive. Publishing a paper packed full of enormous, scary looking expressions is impressive. Merely saying that "we used AD and it worked just fine" is unimpressive.
For decades now we've been incentivizing intellectual wankery over practical utility.
http://www.newsteelconstruction.com/wp/wp-content/uploads/Te...
Besides, the set of problems you can solve is different from the set of problems you can solve quickly. When discussing analog and digital computers, the speed difference isn't all that relevant, but you seem to be confusing them here. Quantum computers do not solve any problem you can't solve on a classical computer, they just solve some faster.
What I'm saying is that even quantum annealers aren't really faster at any practical problem than a comparable supercalculator as of yet.
A much simpler example where naive numerical methods do not work, is any first-order equation with converging characteristics. For example the inviscid burgers equation u_t + u u_x = 0. Even if you start your evolution with a smooth profile, it will form discontinuities. When you try to discretize it, computing derivatives by finite differences does not work at all, and the simplest upwind schemes have a lot of diffusion (which does not correspond to the model).
Probably just a typo, but it's not hard to find particular solutions. The question is more whether solutions exist for all reasonable initial conditions. Here's a famous particular solution:
https://en.wikipedia.org/wiki/Taylor%E2%80%93Green_vortex
I've used a variant of this one to test CFD software.
The Millenium prize problem has a succinct statement of what's under question:
> In three space dimensions and time, given an initial velocity field, there exists a vector velocity and a scalar pressure field, which are both smooth and globally defined, that solve the Navier–Stokes equations.
https://en.wikipedia.org/wiki/Navier%E2%80%93Stokes_existenc...
Keep in mind that this is for incompressible Navier-Stokes with a constant viscosity. For inviscid flows you could get discontinuities as you've indicated with the inviscid Burgers equations, and I know that existence and uniqueness problem for the incompressible Navier-Stokes equations has been proved for certain uncommon viscosity laws (which should be reasonably realistic as a constant viscosity is not quite right).
(And of course there are other complications not considered in this problem like boundary conditions.)
Indeed, a fluid eternally at rest is surely a solution :)
Monte Carlo methods are used to solve partial differential equations, I found both approaches similar in the sense that they look at how the system actually/could behave, instead of looking at the equations solely.
You're not really simulating every outcome, just a "large enough" representative sample.
As an aside, my dad was a chemical engineer and Newton-Raphson was his equivalent everything-is-a-nail numerical method. We used to use brent root and monte carlo simulation in the same way.
Numerical methods are awesome in general.
https://en.m.wikipedia.org/wiki/Field-programmable_analog_ar...
These aren't "hard" problems, they're simply questions that don't make sense. Is finding an odd number that is divisible by 2 a "hard problem"? I don't think so, it's just that it turns out that it doesn't make sense to ask the question.
Some of these "hard problems" actually have solutions that demonstrate they aren't solvable, and these solutions are fairly elegant, in which case I'd also say these are not "hard".
By randomly walking this graph, starting from the current plan and randomly flipping precincts, you can build a distribution of how compact the plans you saw were (there are some measures of compactness defined in TFA and the document linked below), and identify outliers, which are likely to be gerrymandered.
[0] https://sites.tufts.edu/vrdi/files/2018/06/md-report.pdf
And indeed, that's mostly a social solution in it's implementation.
Statewide votes are mostly done by popular vote, so they're not affected by gerrymandering. Nationwide votes like the one for president are not done by popular vote, but they're also not done by district, so gerrymandering doesn't affect them.
1. It lets politicians create districts that will vote for them no matter what.
2. It lets politicians waste opposition votes by putting them into districts that will, overall, just barely vote the other way.
The problem is that these two visions of "the problem" directly oppose each other. #1 says that the problem is districts that vote an 80/20 split. #2 says the problem is districts that vote a 51/49 split.
> Republicans won 57 percent of the vote in contested races in 2016 and won 43 of 50 seats. In 2018, Republicans won the same percentage of the vote in contested races — but won 56 of 63 seats.
> That’s how gerrymandering works. Even the fact that so many more Democratic seats are uncontested is by design: By making certain districts heavily Democratic, many others can be more easily made slightly Republican.
https://www.washingtonpost.com/politics/2018/12/04/several-l...
This stuff works, it's easy to see the effects in heavily gerrymandered states.
Something I just realized is that it will always be that way!
Democrats do better in cities (in general heavily democratic), while Republicans do better in rural areas (typicaly Republican, but not in a dense way like a city would be).
So if you divide districts naturally by geography they will always appear gerrymandered in Republicans favor.
That's kind of my point: No it is not. Districts are meant to be contiguous geographical areas.
Even if you adjust the geographical size of each district to have similar population sizes (which was your point), my point still stands: Because of the geographical nature of districts, cities will always have a larger Democratic percentage, and it will always look like Republicans have gerrymandered things.
It won't look like Republicans gerrymandered it to their advantage, because they won't have the advantage.
The "cracked" districts will vote for you no matter what, but certainly not at 80/20. You're looking for 51% + a safety factor of 10-20%.
Let's say you have parties representing 10%, 20%, 30% and 40% of the population respectively. Ideally, you'd like the politicians elected in the same proportions. In reality if the populations are dispersed evenly, then when you divide up the populations into seats and elect one representative from each seat you are going to end up with some mix of the 30% and 40% making up 100% of the parliament. If the distribution is perfectly even and you are using FPP then the entire parliament will all be from the 40% - which is more of a dictatorship by the 40% than a democracy.
Gerrymandering, and a "fairer" voting system like instant runoff might alter the break up of the 30% and 40%, but either way the 10% doesn't get a seat. To have any say at all they have to vote for one of the 30% or 40%. In other words you end up with a 2 party system, which is of course what we do have. Neither getting rid of gerrymandering nor using a better voting system actually solve the problem, if the problem is ensuring parliament reflects the voting population. Yet we see those two things proposed over and over again here on HN and elsewhere.
The solution is what the other posters in this sub-thread mention. Germany and NZ use it. To me, it looks to have worked very well for them. But getting there is hard as the incumbent 2 parties will combine to oppose it. The change always makes them lose seats to the minorities.
Of course that would be outrageously unfair, with politicians choosing which districts they win rather than voters choosing the politicians to represent them, and yet that is somehow an improvement over the current system of gerrymandering.
A slightly less extreme option would be for the districts that get flipped to be decided by where a given party came closest to winning (the "best near-winner" system used in Baden-Württemberg), but really the aim of this system is to remove all incentive to gerrymander in the first place, so this result flipping rule would never have to be applied.
Having more representatives than districts seems like it would be an overly-ambitious cultural shift in the US, whereas my proposal keeps the familiar 1:1 correspondence, even if there is gerrymandering. It also doesn't change the ballot papers or counting process; and, if gerrymandering is successfully disincentivised, the process works exactly the same as under the existing system.
[0] https://en.wikipedia.org/wiki/Mixed-member_proportional_repr...
Math: Assume 900 people, so 495 voting for the popular party and 405 for the unpopular party. Put 100 popular voters in district 1. Split the remaining equally (395 popular, 405 unpopular). All districts except the first will be won 51%-49% by the unpopular party. (This is the "pack and crack" gerrymandering strategy, packing the party into some districts and cracking them across the other.)
Of course, if you adopt something like STV in small (say ~5 seat) multimember districts, the opportunity for altering representation by how you draw district lines goes way down, and you still retain individual candidate accountability to the general electorate (unlike in party-list proportional schemes).
The problem isn't “how do you draw lines fairly in single-member, FPTP districts”. The problem is single-member, FPTP districts.
Yes.
> It'd take a constitutional amendment to alter the single-member, FPTP practice, wouldn't it.
Nope, the single-member district requirement is a federal statute that was adopted in response to states turning to, or at least considering, multimember at-large FPTP districts (majority-take-all) to prevent effectively enfranchising minorities (well, specifically blacks). Which was certainly a good motive, and single-member FPTP districts are better than that, but the same law could be retuned to prevent that but allow (or even require, in states large enough to support it) multimember districts with a candidate-centered proportional scheme like STV.
Suffice to say that it would take a federal statute to allow MMD outside of NM and Hawaii? That still seems like a heavier lift than passing state-level gerrymandering reform.
And they don't need to be set against themselves anyway - if MMD were allowed, state-level gerrymandering reform is still valuable, for those that stick with single districts.
Unless you're talking about a federal law to mandate MMD, which is even harder.
Although I do like the standard that was suggested in the Wisconsin case, the one that Kennedy chickened out on before he retired. Sorry, I forget the details - something about minimizing wasted votes.
1. Create districts that will overwhelmingly vote for the other guy.
and
2. Create districts that will just barely vote for you.
Because it doesn't matter if you win a district by 1% or by 49% you can take a population that overall is 50/50, or even prefers the other guy and create a lot of districts that will vote for you by a small margin, and only a handful of districts that will vote for the other guy but by a really big margin.
There's actually an android puzzle game that does a great job of communicating how it works: https://play.google.com/store/apps/details?id=com.studioBlim...
> To the extent that a politician is benefiting himself in style #1
There's no possible benefit to a politician in winning a district 80/20 rather than 60/40.
edit: If 6 people want to vote for me, and 6 want to vote for you, I want to put 3 of your voters in one district, and have three more identical districts each with 2 of my voters and 1 of yours. The first district is what you're referring to as Type 1, and the other three are what you're referring to as Type 2. If you can find a more ideal districting arrangement for my party, I'd like to hear it.
No, you're just not bothering to read my comment. I'll repeat it.
There are two (2) arguments commonly advanced toward the idea that gerrymandering is bad. In summary, they are:
1. Creating safe seats;
2. Nullifying opposition votes.
More of one means less of the other.
The way it works now is that you create a perfectly safe seat for the other party in exchange for many more fairly comfortable seats for your own party. The maps are not drawn up to make individual incumbents happy, but to maximize party power.
The fairly comfortable seats may still be "safe" in normal elections- they're not 100% a sure thing, but they're not particularly competitive and elections can be reliably fought and won cycle after cycle. You can't just not campaign, but the other side has one hand tied behind their backs, so as long as you have a competent campaign and no sex scandals, you're fine. Whether that's the sort of "safe seat" people are talking about I couldn't say.
The handful of ultra-secure opposition seats created by (1) are more like an unfortunate byproduct of the truly foul (2).
The party in charge of drawing the lines will—as a side effect–create some safe seats for the minority party. And in doing so, will retain control of the legislative body, by having a larger number of districts they can win.
Also, I've mostly heard the second argument made, not the first. A large party's leadership should probably lean in that direction anyway, not caring as much about the individual official.
What about the rural states, you say? Well they still get to manage their own, internal affairs with their own legislature, governors, etc. But as far as state-level decisions are concerned, their weight should be exactly equal to that of their population representation.
Every open cover has a finite subcover.
My idea - I welcome counter arguments - is to calculate the district's center of mass and find the furthest point the district still contains from that center of mass. Then create a circle with that distance as the radius and find the percentage of _land_ (maybe even privately owned land?) within that circle that is in the district. My view is that the percentage should be something like 50% (maybe higher? Hard to say without actually designing districts and checking the numbers).
50% would mean that half of the habitable land remaining in the circle could be a different district but no more.
Instead, you can simply put down a finite number of points on a map and define the districts using polygons (connect the points with straight lines.
If you have 2 islands with three bridges connecting them, you could just walk them trivially, yet there are an uneven number of connections on each node.
I'm not sure how it could work if any nodes had odd degree.
Or you can just not stop, and try to go even deeper. But then you stop being a mathematician, and you turn into a madman, a philosopher or a theologist.
It's not impossible to gain understanding of a step in someone else's argument.
There may also exist types of math that are impossible to represent or reason about with current notation.
[0] https://en.wikipedia.org/wiki/Terence_Tao
[1] https://mathoverflow.net/questions/366070/what-are-the-benef...