Why Discrete Math Is Important | Hacker News Reader

Why Discrete Math Is Important

artofproblemsolving.com

297 pointsjaoo124 comments

Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient.

Once I wrapped my mind around this, I started to understand something. Manifolds are just graphs with many vertices. Fourier analysis studies the eigen-decomposition of the laplacian on a graph, and is used to solve heat, wave and dispersion equations. Stokes theorem (which in a discrete setting amounts to matrix associativity) is a self-evident fact. Most of applied math is thus reduced to a few lines of octave code.

Only when you lose discreteness or compactness things start to get nasty. But this is just a flaw in our current definition of real numbers.

I am intrigued by your ideas and wish to subscribe to your newsletter. How does Stokes' theorem in a discrete setting just amount to associativity?

(I wondered about the sort of discrete differential geometry found e.g. here https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf and here https://arxiv.org/pdf/math/0508341.pdf but in that setting the situation seems to be more "Stokes' theorem is true by definition".)

I am intrigued by your ideas and wish to subscribe to your newsletter.

Lol, this is not the first time that I am mocked here :)

How does Stokes' theorem in a discrete setting just amount to associativity?

Manifolds are modeled by graphs, and calculus on manifolds becomes linear algebra using the matrices naturally associated to these graphs.

Consider a graph with n vertices and m edges.

The most important matrix is the oriented incidence matrix B, of size mxn, that has a single +1 and a single -1 on each row, indicating the vertices connected by the corresponding edge.

Scalar fields := functions defined over the vertices = vectors of R^n

Vector fields := functions defined over the edges = vectors of R^m

When you interpret matrices as linear operators:

    B     : R^n -> R^m is the gradient operator
    -B'   : R^m -> R^n is the divergence operator
    -B'.B : R^n -> R^n is the laplacian

A subset of the vertices is given by a binary vector M \in R^n. The integral of a scalar field f over M is M'.f

The outwards boundary of a subset M is -B.M. The flux of a vector field F through this boundary is (-B.M)'.F

Stokes theorem is thus the trivial identity (-B.M)'.F = M'.(-B'.F)

(I use a dot for matrix products because the star breaks the formatting. You can also define the divergence without the minus sign, but I like my laplacians to be negative-definite, it feels weird otherwise.)

I didn't actually intend my comment as mockery. I'm very much for finding correspondences between discrete and continuous things. I just didn't see how to set things up so that Stokes turned into associativity.

I think this is in fact the same thing as the "true by definition" found in the second of my links above -- but I hadn't thought hard enough about how that cashes out concretely to see that you can express it as the associativity of a three-way product. Nice.

stokes theorem is often written (in a continuous setting) as

    < dM, F > = < M, dF >

(the adjoint of the boundary operator is the exterior derivative). In the discrete case, these integrals are actually products of matrices. There is nothing too deep here.

Edit: regarding the "true by definition" issue, you can do one of two things. (1) Build the definition of the boundary and exterior derivative independently and then verify that Stokes theorem holds. Or (2) build the definition of only one of these two operators, and then define the other one as its adjoint. In that second case, Stokes theorem is true by definition. But it doesn't matter too much, these are just two different ways to write the same thing.

Nice thing about "continuous" math is that we have so many "standardised" tools in its toolbox, contrasted with "ad-hoc-edness" of discrete math. Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/

You can also see it in the opposite sense.

The continuous models are an ad-hoc, purely mental, construction. When you have to solve a PDE, you actually build a discrete model (using finite elements), and solve the discrete thing. Except in very simple toy problems, you can never "solve" anything using only continuous tools.

Spectral methods, or any methods where you have chosen a basis of continuous functions and are solving for weights produces solutions in the continuous domain. That's not a discrete model.

The grandparent poster might like Chebfun, http://www.chebfun.org

>Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/

I'm often interested in the opposite: Solving continuous problems by going to the discrete domain.

I'm not a mathematician, but I did enjoy taking math courses and dabbling a little.

My personal highlight was when I was struggling for months to solve a continuous variable problem, but then one day I decided to "pixelate" it and converted it to a discrete problem. I solved the discrete problem, and got the answer to the continuous problem by taking the limit of the solution.

The problem was: If you choose n numbers at random (uniformly) in the interval (0,1), what is the expected value of the maximum?

I showed this problem to a number of people (including math professors) who struggled with it. Finally, one day, a colleague solved the problem in 5 minutes and 3 lines using continuous math. (It's not a clever solution either - surprising so many people missed it).

Still, I feel content with my discrete proof (which was about 2 pages). Since then I've often thought I should collect interesting continuous problems solved this way and put them on a web site, but never did. :-(

So is this the solution? The probability that all numbers are less than x is equal to x^n. So then you take the derivative of that to get the probability that the maximum us is exactly x. n x^n-1. Then calculate the expected value as integral from 0 to 1 of x n x^n-1 = n/n+1.

Too lazy to think deeply about it, but it sounds right. You start with the cumulative distribution function and get the pdf from it, which looks like what you're doing.

Really simple solution. Problem is simple enough that this could be a standard HW problem in a probability course. Yet so many people (including myself) did not see it. We kept doing multiple integrals (n integrals for n points) and tried using induction on it.

This was actually a subproblem of the real problem. The real problem was: Given n points chosen randomly on a circle, construct the n-sided polygon. What is the probability that the center of the circle is inside the polygon? Since I worked on it, the problem has shown up on the Internet in various places (usually for the special case of n=3 - triangles, but I think I've seen the general one posted here and there). I don't recall if anyone came up with the same solution I did for the general case - I think one site had it.

it is (a standard HW problem). for bonus points, there's a connection between order statistics of the uniform distribution (such as max) and the beta distribution, of which the solution above is an example.

>because the universe is discrete

Many aspects of the universe are not known to be discrete, such as space, time, energy, and much, much more. It's not unreasonable that there are discrete and continuous aspects to the universe.

Many things that pop science treats as discrete, such as an electron, are most accurately described as interactions of a continuous fields via topological quantum field theories. Treating the electron as a discrete thing only works for some experiments. Treating it as a field works for all experiments.

"not known to be discrete" does not imply "It's not unreasonable that there are discrete and continuous aspects to the universe"; it is not known that anything is continuous either.

The theories that best model every known experiment are continuous. General relativity models large scale phenomena to incredible precision, and is continuous. Predictions made by it around 100 years ago are still being tested and found true, such as gravitational waves.

The Standard Model, which models everything else, is continuous. A specific part of it, QED, is the most accurate theory known, agreeing with experiment to better than 10 parts in a billion.

There is no known violation of these two theories, which explain all of the observable universe. There is an issue on how to glue them together, and one of the leading methods, string theory, is also continuous. I am unaware of any theory that can replace these that has no continuous parts, such as symmetries.

> it is not known that anything is continuous either

Every physics theory that we use to explain the universe is continuous, and not a single one is not, so I'm betting that there are continuous things in reality.

Other leading theories are non-continuous. LGQ example is an active area of research.

> Every physics theory that we use to explain the universe is continuous

Are you suggesting thete are no discrete models?

Any discrete model may be similar to leading continuous models, so the explanatory power of both isn't relevant unless it can only be produced by continuous models.

>Other leading theories are non-continuous.

Which theories discretize all variables? I'm well aware people make models all the time, but they usually fail to explain all we observe or are toy models, like 2D TQFT models, not designed to mirror reality, but to fiddle with to see if they extend.

LQG, for example, treats space as quantized at the Plank length, but this has already been disproven experimentally [1,2], forcing LQG to reassess. LQG still has continuous parameters, such as symmetry, and is based on the same continuous math as GR and TQFTs. It's simply trying to discretize (somewhat) spacetime, but it certainly has not yet succeeded at that.

Hogan's holometer experiment [3] also has shown that the scales LQG wanted to discretize spacetime at are incorrect.

So there is at least 2 different experiments invalidating a central piece of LQG. Of course LQG can simply retrench and claim scales are smaller than the Plank length.

There is no experimental evidence pointing to LGQ as reality. It has not even been shown to reproduce GR in the semi-classical limit, so it may end up simply being mathematical fantasy. LQG also has lots of other technical problems that may in the end throw it on the heap of failed theories, of which there have been many. It makes no prediction not already covered under GR.

So, yes, I realize there are people trying to discretize the universe, but so far none of these theories have reproduced what we observe in experiment, and the only theories that have reproduced all we observe in experiment are continuous.

>Any discrete model may be similar to leading continuous models, so the explanatory power of both isn't relevant unless it can only be produced by continuous models.

Which model using only discrete variables can make the same predictions of GR or SM? I cannot think of one, I cannot find one, so it may be that so far the only models that work are continuous.

Heck, even going simpler - what discrete model can reproduce only GR? LQG so far cannot, despite significant effort trying to make it do so. So that surely puts the burden of proof on showing discrete models as equivalent to continuous ones.

So I'm game for something to break current models, because that would be cool. However, nothing has, and no theories is really even close to replacing SM and/or GR.

[1] https://arxiv.org/abs/1102.2784

[2] http://hal.in2p3.fr/tel-01219651/document

[3] https://en.wikipedia.org/wiki/Holometer

> but it certainly has not yet succeeded at that

The claim here is actual "continuous" objects likely exist. How can you demonstrate this?

All continuous models can be reproduced in discrete models up to the resolution of "all current observations", How are discrete models inherently unable to match continuous ones?

>The claim here is actual "continuous" objects likely exist. How can you demonstrate this?

You cannot demonstrate either continuous or discrete beyond what a model shows. All of knowledge in science is from models, nothing more.

For example, all objects that you perceive as discrete are modeled as waves in QM (more specifically TQFT). Given that it seems everything behaves as a wave, how can you prove discrete items exist to the level of proof you seem to require? I doubt it's possible to do so. Your perception of discrete is wrong, according to QM. What was once wave/particle duality in the early 1900s got replaced with larger and larger systems and TQFT until now everything in QM is a field, including you, including marbles, including particles, including everything. And this view allows the theory to accurately predict all relevant experiments. Discrete you, marbles, electrons, fails experimentally.

>All continuous models can be reproduced in discrete models up to the resolution of "all current observations"

This is not true. If I recall my QCD correctly, some calculations spit out infinities if the underlying space is not continuous. I suspect there are other places that add divergences if you discretize things.

Roughly - if you perform calculations in QCD (or QED), you basically add up an infinite number of terms, each with smaller and smaller probability, to get a finite answer (which, for QED, is astoundingly accurate). If you force this infinite sum to not be allowed to go to zero spatially, then you get infinite terms that cannot shrink, and you get an infinity. If you try to fix this by only including a finite number of terms, you get other issues, such as not getting the right answer when tested experimentally.

I also seem to recall that in QED if you do not have continuous space, then the self-interaction of an electron again spits out infinities, which of course is one major impetus for developing QED to begin with.

So no, you cannot simply discretize math and get all calculations to still given the same answers you see experimentally. It's not that simple.

For example, you mentioned LQG - researchers have tried for a long, long time, with much effort, to get it to reproduce continuous GR with a discrete model, and they so far have failed. It is not as simple as simply making the discreteness smaller. There are fundamental issues in getting such things to match the continuous theories.

So, despite it being a really useful thing to do, and despite there being lots of work trying to get a discrete model to match GR or SM, I am unaware of anyone ever making it work.

Interestingly, trying to find a better way to explain it to you, I found this [1] question about the inability of anyone to make a discrete model match current continuous ones (which backs my view that it has not been done, and perhaps will be found impossible). He makes the interesting point that your view of LQG making space(time) discrete is not correct. The reason is that this would violate Lorenz invariance (which is also the thing those experiments listed) are looking at, and so far Lorenz has never been broken experimentally, to the point of pushing it below the plank limit. So the "discreteness" of LQG is much more subtle than a naïve view.

I asked for an example of a discrete theory that matches some significant piece of physics - do you have one or not? Your claim that it can be done is not matched by any evidence you have put forth, nor any that I have ever encountered.

[1] https://math.stackexchange.com/questions/186076/is-there-suc...

I have reviewed [1] and [2] but it isn't clear to me how they prove that space isn't quantized at the Planck length.

Could you explain how these experiments disprove that?

Here's [1] a pop science explanation of that result (and there have been several more in the same vein since then).

A key quote from the article "And given that some quantum gravity frameworks predict that effects should be showing up at that point, perhaps those models are simply wrong, and there is no changing speed of light."

AFAIK, later experiments have even lowered the threshold, making LQG less and less likely, in the same way the LHC results have pushed back supersymmetry arguments by invalidating some versions predictions.

[1] https://www.symmetrymagazine.org/breaking/2009/10/28/gamma-r...

>Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient.

This is not true. There are "things" in the universe that are discrete (for example: matter). But whether the universe itself is discrete is something we don't know.

What is the smallest discrete measurable length in the universe? We don't know.

Would you concede that the Planck length is a good approximation of the smallest measurable length in the universe?

The change in radius of a black hole when 1 bit of information is added is much smaller than 1 Planck length. The Planck length is just a convenient unit of measure in physics. It has no relevance to limits of space or time at all.

Here's an article on the subject:

https://www.quora.com/Is-there-anything-smaller-than-a-Planc...

Interesting. I am now better informed.

Why would the Planck length be the smallest measurable length in the universe?

Edit: To be more clear: Is there a theoretical reason why the Planck length would approximate the smallest measurable length?

> But this is just a flaw in our current definition of real numbers.

The distance between discrete infinite sets (countable) and continuous infinite sets (uncountable) is a pretty large gap. Are you saying that there is no gap? There are pretty well studied proofs showing that uncountable sets are much bigger than countable.

What's your take on this? Got a counter proof to Cantor?

What's your take on this? Got a counter proof to Cantor?

As much as I am a fan of all things about cardinals, measure and category (Oxtoby's booklet on this stuff has been on my nightstand for several months, to a great pleasure), I still fail to recognize its technological and physical implications.

My take on this is modelled after the famous article "The dawning of the age of stochasticity" by David Mumford, where he argues that the current definition of real numbers leads to infuriating contradictions, especially in the light of probability theory. This article left me with the impression that in a near future, we will see a clever definition of "real-valued random variable" that does not depend on the definition of real numbers and avoids all kind of disgusting paradoxes.

> Discrete math is important because the universe is discrete.

Is time discrete?

Unknown. There's at least one approach to quantum gravity based on the idea that it is (causal sets), but we haven't proven it one way or another.

I'd rather ask: Is space discrete? We know there are discrete particles, but AFAIR they can potentially move to any position in the continuum, i.e. for each particle, x, y and z are in the domain of reals (or some huge real interval), not some discrete subset of it.

Or, am I mistaken?

It's the same question (since time and space are not fully distinct), and the answer's equally unknown.

I too have a problem with continuous math. However I have to wonder if we didn't have our senses, would our imaginations be discrete or continuous?

Discontinuous, probably.

Or concrete, as suggested by Knuth, Graham, and Patashnik in their book, "Concrete Mathematics: A Foundation for Computer Science".

https://www.amazon.com/Concrete-Mathematics-Foundation-Compu...

The "Concrete Math" book title is a play on words - combining continuous and discrete. From the preface: "When DEK taught Concrete Mathematics for the first time.... [h]e announced that, contrary to the expectations of some of his colleagues, he was _not_ going to teach the Theory of Aggregates, not Stone's Embedding Theorem, not even the Stone-Cech compactification. (Several students from the civil engineering department got up and quietly left the room). [Edit]: Typo/Spelling fix.

Neurons themselves are working on physics at not quite quantum scales, so probably a good model would be timewise continuous stochastic.

>Manifolds are just graphs with many vertices.

Okay, I'll bite. How? What is the definition of the tangent space? Dimension?

Yeah you'll want hypergraphs (or even better simplicial complexes) in general but you can make sense of manifolds as discrete objects. In fact I'm fairly sure you can triangulate any (smooth?) manifold.

The tangent space can be defined in terms of derivations, as soon as you define what a smooth function on the 'discrete' manifold should look like (you may have to define the derivative at a face, rather than a vertex, or have the function take values on faces rather than vertices).

Sure. I think the notion of a manifold wouldn't be very interesting if it didn't have some kind of discrete analogue. But, for me at least, smooth manifolds are much easier to think about than simplicial complexes or PL manifolds.

the tangent space is the set of edges

vector fields (sections of the tangent bundle) correspond to real-valued functions defined on edges

dimension is always 2 ;)

if you want higher dimension you have to consider higher-dimensional cliques beyond edges (that are 2-cliques): triangles, tetrahedra, and so on. But very often this is not necessary, even when discretizing 3d stuff. For example, for Poisson equation, and the associated classical pde, you only need the laplacian, which acts on functions, regardless of the dimension.

That seems a weird choice of tangent space, surely a circle and a disk should have different tangent spaces?

And they do. When you discretize a circle as a graph, all the edges are along the boundary. When you discretize the disk, you fill its whole interior with edges in all directions.

Is a triangle a circle or a disk?

> Only when you lose discreteness or compactness things start to get nasty. But this is just a flaw in our current definition of real numbers.

What "flaw" are you referring to? Also you're certainly free to use other definitions for real numbers, if you feel they better capture "reality".

The problem I've always had with real numbers is that the vast majority (i.e. uncountably many) of them are not computable, and only countably many of them are computable.

That means that almost every real number, all but a vanishingly small subset, cannot be represented by any means whatsoever. No formulas, no algorithms, nothing. On top of which, they're surprisingly complicated to construct. There's several different ways of doing it, and they're all complicated.

At some point you've got to ask yourself, "are they really even there?" (Of course, those who already have non-Platonic leanings will find that question amusing.) I start to think that maybe we'd be better served by dropping all the non-computable numbers and start doing almost everything in the field of computables.

All definitions of real numbers are equivalent, as far as I know. And as much as I love the definitions of R as a crowning achievement of human civilization, they lead to some infuriating paradoxes, especially in measure theory (e.g., freiling's axiom of symmetry).

Hello Doron Zeilberger. Did not know you read HN.

Apart from his interesting ideas about infinity, Zeilberger has things to say about math contests. See http://sites.math.rutgers.edu/~zeilberg/Opinion71.html I'd love to find a modern equivalent of the "gilyonot lematematika" he mentions.

> Many students, especially bright and motivated students, find algebra, geometry, and even calculus dull and uninspiring

That was me. I grew up believing I hated math. Struggled all the way through middle & high school to AP calc and just found it incredibly boring and tedious. Ended up opting out of doing engineering/science in undergrad because I just couldn't stand doing all the math.

Long story short, years later ended up going back to school for CS and took discrete math as one of my first courses, and remember being blown away by how cool it was. All this time thinking I hated math!

Hard to say exactly what the difference is. Partially I think my brain just groks discrete concepts more easily.

But also the class had a heavy emphasis on proofs, which I think was really important. At a certain level this type of problem-solving can start to resemble philosophy. Chugging through a proof, figuring out just the right way to construct it and slapping a triumphant "Q.E.D." at the end is an empowering experience, especially the first time. There's a world of difference between "you throw a ball, solve for its velocity at time x" and "prove that there must be a ball" (I'm embellishing of course). It's a difference between obtaining an answer for a specific instance of a situation, and shedding light on some fundamental/universal property of the world. To me that feels profound in a sense, which makes it exciting.

Proofs don't belong solely to the domain of discrete math, of course, so this probably isn't as much a testament to the subject as it is to the general problem-solving approach. It would be nice if students could get exposed to this a bit earlier, I think there are many folks like myself who would realize that they can love math too.

What you're describing is the basic shift between what lower-ed science/math is like and what "real" (college) science/math is like. The problem is that everything they teach in highschool and below needs to have an escape hatch for "what if they have anti-ADHD* but no clue what's going on?" That's why you were able to solve for v without obtaining any knowledge about the universe, and why taking discrete math did what they claimed geometry would do.

* It's kind of a stupid way to put it, but by anti-ADHD I mean sufficiently controlled behavior combined with the ability to focus on any rote task until it is completely learned (basically, whatever traits or life conditions you need to have the opposite of ADHD). No matter what, you're not allowed to fail that group.

> anti-ADHD

awkward way to put it (although i dunno how else to describe them), but i think everyone knows the students you are talking about. these people are the reason why highschool math/science is hell, and you can't get away from them by taken honors or AP courses.

Don't worry, algebra, systems of linear equations, synthetic geometry, analytic geometry, infinite series, differential and integral calculus, etc. can also be made 'cool' and intellectually stimulating. Likewise discrete math can be made dull and lifeless. The difference has much more to do with quality of problems and teaching than with your brain.

> even calculus dull and uninspiring

Calculus is totally based on the teacher. I had an awesome Calculus teacher (He actually was a Physicians Assistant and had degrees from Yale and Harvard but volunteered at my small Christian School). He taught me first class why calculus was awesome by challenging use that everything else in math was fake numbers. Showed us the difference between 1/3 and 0.33333 and studying the speed of two trains word problem was always wrong. He than stated that with Calculus you could see the world as we see it. We than used functions all semester long that would eventually get "exact" and it was an awesome ride. To bad we had 3 students and the other 2 were total math geniuses and got perfect math scores on their SATs. They always made me feel like an idiot.

> It's a difference between obtaining an answer for a specific instance of a situation, and shedding light on some fundamental/universal property of the world.

They're also completely different questions in the sense of what you mean when you say "this result is correct."

The ball velocity is really a simplified model that gives you a correspondence truth (you verify by running the experiment and taking a measurement.) The exidtence proof gives you a coherence truth, i.e. there are no unknown factors and ur statement is absolutely true.

Just giving terminology to your intuition: coherence truth vs correspondence truth.

That's a great way of putting it!

Even if we don't teach a single day of number theory, I think we can all agree that modern society would be better if everybody had to have a semester of basic probability or statistics as part of their education.

Not really. You have to find a way to make the math real to your students or else it becomes just another exercise of "what set of words do I need to say in order to make the teacher happy". At least in my experience, most learning seems to be either incidental OR some sort of vestigial residue of the social component of making the system happy.

What? You can make easily make basic statistic and probability about real problems and interesting. Talk about sports. Talk about risks of the stock market and financial planning. Talk about politics/polling. Talk about gambling/poker. Just takes an interesting teacher to make any subject interesting.

Like, I want to believe you that such a thing is easy. But I'm not really convinced by the assertion that it is followed by a non-descriptive blurb. I mean I get what you're saying, "Find what they care about and try to apply statistics to it." However, I don't believe that this process is easy.

Sports is a good example of why I don't think this is easy. What exactly is the point of statistics in sports? Predicting what teams are going to win or what strategies are superior. Most children in school are not interested in sports because they're into strategy or because they're predicting who's going to win. They're interested in it for social reasons. Which team do their parents or friends want to win. Telling everyone at thanksgiving that the family team is going to lose the game will probably not go well for them. And as far as strategy goes ... I thought the statistical analysis of the extra point kick in football indicates that you should never do it. Teams rarely make use of this at the professional level. Also didn't they make a movie about how nobody pays attention to the math in baseball (Moneyball?). Anyway, if adults who have money and fame on the line can't be bothered to care about statistics in sports, then I don't see how children are going to be much different.

Of course that's where you come in. You say it's easy. Personally, I would love to see why you think this because it looks hard to me. I look forward to a more in depth response from you.

Well I'm commenting on the internet Verdex_3. I'm not going to take the time to write out a bunch of interesting statistical examples for you. I wasn't trying to say it's easy to make statistics interesting. Was only trying to refute what I thought that you were asserting; statistics and probability are not interesting to teach. Designing enjoyable, interesting, challenging and fair curriculum is a really hard task to do for any subject...

If you don't believe math can be made interesting I would checkout websites like FiveThirtyEight or youtube channels like numberphile. It's definitely possible to describe statistics or math problems in interesting ways. It's hard to make any class interesting, but any teacher can do it if they work at it hard enough.

Also your moneyball comment makes no sense. All teams operate like the 2002 Oakland A's now, if anything the the movie shows the triump of statistics over bad heuristics.

Trick 'em into thinking they aren't learning and they do.

https://www.youtube.com/watch?v=elTCEVAAEfo

Talk about medical screens and their interpretation (eg., https://www.youtube.com/watch?v=Ql2jEJ-6e-Y)

You propose we stop teaching children to count? That two comes after one, is one more than one etc? I don't think we can get away from all discreet math... ;-)

Just pretend the numbers are real :P

I have to admit, being a hybrid math/csci student, I never understood the place of discrete math in mathematics or computer science. It always seemed like a mish-mash of different topics I'd studied in algebra->geometry->calc (including mv calc, linear algebra, diff eq, and series and sequences)->real analysis. This article is a bit too brief to properly place it (at least I still don't see it), could someone provide some proper context for discrete mathematics that fits into the mold of the standard maths sequence?

It's hard to place a particular "context" for discrete math; it really is a hodgepodge of topics, loosely linked because they deal with discrete structures (integers, graphs, logic statements) rather than continuous ones (real/complex numbers).

It's particularly relevant to computer science because, in CS, we're dealing with discrete structures almost exclusively. The rise of computers and of CS is both what led to the current interest in discrete math subjects as a research field and what led to the development of university curricula in the topic.

So, really, discrete math (as a university course) exists mostly to teach some CS-relevant topics that don't necessarily get much dedicated time in the "standard" algebra->geometry->calc progression, because they're more concerned with continuous phenomena. It's sort of a parallel and independent track from the "standard" math sequence.

It gains a bit more unity when you try to interpret it through certain lenses.

In particular, one problem with discrete mathematics as it's taught, is that it doesn't separate the methods of counting from the set of objects that you need to count.

There are a couple of ways around this. One good way is to look at all combinatoric identities as referring to the number of ways you can connect some set to some other set. Sometimes they're called "choices", "mappings", functions, whatever. You can talk about the function and sets separate from the numbers, and the numbers drop out of properties of the set. Doing this removes a layer of interpretation and guesswork even if it ups the abstraction a bit.

Additionally, discrete math just looked at as the math of algorithms also gets you far. Sedgewick's Analysis of Algorithms book is actually a discrete math book in disguise, since it gives a system of notation that can describe basically any combinatorical object separate from the counting method -- and then maps it to the counting method.

https://www.amazon.com/Introduction-Analysis-Algorithms-2nd-...

So all responses thus far have been great, I think the thing I struggled with in HS and into university is trying to place everything and see what the current math leads to. So, responding here, but upvoting those that responded to me at this time because all provided me with insight. Thanks!

Head down the Prof Wildberger rabbit hole if you'd like to explore why we might be able to cast aside chunks of conventional math including real numbers and infinite sets. https://m.youtube.com/channel/UCXl0Zbk8_rvjyLwAR-Xh9pQ https://njwildberger.com

I would be careful taking that stuff too seriously. It's ok as entertainment though.

Might be? Of course we can. Obviously infinite objects are irrelevant to modeling the real world. They are just a shorthand for adding a bunch of annoying qualifiers to every mathematical statement.

> Obviously infinite objects are irrelevant to modeling the real world.

I disagree. The concept of infinite objects are essentially object sets with an unknown limit. This represents a general case from which we can draw important concepts.

It's a good thing we don't actually need the square root of two!

I disagree that CS deals only with discrete math. Machine learning makes heavy use of linear algebra, with a decent amount of calculus to model statistical phenomena. All of this uses continuous variables, not discrete.

A computer still deals with a finite amount of bits (e.g. 32-bit floating point numbers) so its a discrete system that is large enough to approximate a continuous system.

It may not matter much in practice except for numerical precision issues, but it is useful to understand the foundations and occasionally throw away abstractions for performance/other requirements.

Even then, only small subset of discrete maths often called numerical methods is needed. (Discretizaton, discrete linear and nonlinear algebra, stability.) Going at a problem from fully discrete math point of view is often suicidal (results in unworkable algorithms) as integrals or difference equations are much more useful in practice than say discrete combinatorics. (Mostly used in cryptography.)

Graphs are sometimes useful in a narrow set of CS problems, as are similar structures. However, these are often not taught at discrete maths courses.

That's silly. Floating point math is an approximation of continuous math. It's only discrete in a narrow technical sense.

Computers don't just do floating point. And when they do it, at the lower levels, they don't do it as floating point.

A survey "Discrete Mathematics" course is definitely a mishmash. But every topic in discrete mathematics is rich enough to study in it's own 4 credit 1 quarter undergraduate course: Set Theory, Combinatorics, Graph Theory, Formal Logic, etc.

It doesn't. In my experience, "Discrete Math" is not offered as a math class, but rather as a computer class. In effect, it is the "math for computer science majors" class.

At the university I went to both the math and CS departments offered discrete math courses with slightly different focuses.

That was not my experience despite it being a requirement for the CS major.

Discrete math in my school is mostly about combinatorics, but also graph theory, trees, and things like that. It doesn’t really fit into the standard math sequence IMO. The standard math sequence is essentially single-variable calculus -> multi-variable calculus -> linear algebra and differential equations -> real analysis. Note that all of the above fields essentially operate on continuous things like the real numbers.

That's not quite true, almost any respectable math program is gonna include a significant amount of material on finite set theory and discrete algebra (though maybe not in the non math major escalator, that usually stops at differential equations). That said, I think there is definitely a place for a "discrete math" course, which focuses on teaching things in a more computer science relevant manner.

I also think numerical analysis is a much better choice than real analysis for CS majors, but that's a different topic...

Oh I’m interpreting GP’s mention of standard math sequence as something everyone in math/CS/engineering needs to study, not what math majors specifically need to study.

Of course applied math is much more relevant to CS than pure math. CS is an application of math.

But most applied maths courses/books focus heavily on ODE/PDE which are rarely of help to CS undergrads.

A common use case is prove correctness or running time of algorithms.

Prove running time as in complexity analysis is more analysis than algebra though, right?

Depends. There's not a whole lot of analysis you can do on sufficiently complex recursive algorithms.

> Prominent math competitions such as MATHCOUNTS (at the middle school level) and the American Mathematics Competitions (at the high school level) feature discrete math questions as a significant portion of their contests. On harder high school contests, such as the AIME, the quantity of discrete math is even larger.

As someone who participated in these contests, this isn't the entire story. Competitions such as these all require numerical answers, and as such skew extremely heavily towards counting and probability (as in, there's no other discrete math topics but these two). It's only when you get into proof based contents that the real meat of discrete math, namely recurrence, cardinality, graphs, etc. start showing up.

The vast majority of people who learn calculus in school will never model a changing system in their life again.

The vast majority who didn't take statistics courses in college will still try to use the limited understanding they have of statistics to assess statistical claims or draw conclusions from reported figures. The vast majority of people who never took discrete mathematics courses will still face problems of figuring out the difference of combinations and permutations at some points in their life.

I love calculus and I'm very happy I know it but I would be lying if I said it even approaches the importance of discrete mathematics and statistics in today's world.

I love discrete math, it seems so much cleaner in general. I wish there were more reformulations of calculus, other numerical methods into discrete maths.

I think Knuth’s concrete mathematics might have been an attempt at this, but I’ve never found time to dig into it in depth. Perhaps I should try again...

Discrete calculus is a thing [0], although it is not so much a reformutaltion of infinitesimal calculus as it is its own field that borrows heavily from calculus.

[0] https://en.wikipedia.org/wiki/Finite_difference

In some sense, don't the modern formulations of real analysis, etc. already start from as close to discrete maths as you can get (set theory)?

Sets -> Naturals -> Rationals -> Reals

I don't understand how you could reformulate study of continuous structures into discrete math in any sense other than the above.

Every mathematical object (ok, this is false but that's not the point here) can be constructed in ZFC (the standard axiomatic framework for set theory) so you can construct the real numbers in terms of sets (if you want more precise informations on this construction look up Dedekind cuts).

However this is irrelevant to, say, analysis, you could define the real numbers as the unique (up to isomorphism) complete, ordered, archimedean field and do analysis just as well, so I'd say that you are right in some sense and some formulation, but it's a bit of a stretch to consider analysis as starting from discrete maths.

I also don't see how set theory fits into discrete maths, apart from the basics it seems pretty far from the common structures studied in discrete maths.

Pick the Grothendieck-Tarski axiom instead, and use category theory to build ZFC via topos. This path is "big" enough to handle all the interesting sets; it can't deal with proper classes, but proper classes are kind of metaphysical anyway.

[0] https://en.wikipedia.org/wiki/Tarski–Grothendieck_set_theory

Sure, but ZFC by itself also deals with every interesting set, I was just being nitpicky of my own assertion.

I'm not familiar with TG, what's the relation between it and ZFC+some large cardinal axiom?

I understand that it's a stretch; thus the "in some sense" and "close".

See my last sentence. It's not clear to me how you could reformulate analysis, which in many ways is the study of the infinite, into discrete maths in any way other than the very loose sense of starting with ZFC.

I loved Knuth’s concrete mathematics too. But I don’t think it is an attempt at reformulating calculus into the discrete math framework. Instead in many places in concrete math, knowledge of calculus is assumed, especially in later chapters about generating functions etc.

He did elsewhere suggest teaching calculus by Big O notation: http://www.ams.org/notices/199806/commentary.pdf

I would be excited to see someone try that.

UPenn's Calculus I+II courses with Robert Ghrist uses this sort of notation right at the beginning (it takes the Talyor Polynomial as the natural starting point, rather than derivatives, with knocking off terms of the summation involves factoring them out into the O-notation block).

I found his original and not abbreviated version

https://www-cs-staff.stanford.edu/~knuth/calc

Now, how do I TeXify it on an iPad?

I've TeXed it a while ago; scroll down here: https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a...

What you're looking for probably either already exists, or doesn't make any sense, depending on how you clear up the ambiguities in what you've said.

1) I loved my undergraduate discrete math class.

2) who can't love a class that teaches you how to understand the math behind poker :)

Symbolic logic / truth tables is the single most useful subject I have ever taken wrt programming. It provides an intuitive understanding of conditionals so they can be expressed simply and clearly.

Attention parents of "mathy" kids: A bit off topic, but I just want to put in a testimonial for AoPS online math classes. My daughter used it as the spine of her middle/high-school math education. Great program. Check it out.

Fully agree - the whole AoPS range of books and courses are just amazing. Highly recommended for all kids.

I wish I had paid more attention to or had a better instructor for my discrete mathematics course, I find many of the topics covered in it extremely fascinating now, years later. :(

Surely, online resources for these courses must exist? I guess it's just about finding the will and time to put in double the effort because of a lack of instructor/conducive environment.

The Coursera/UC series on discrete mathematics [1] looks like a good introduction.

[1] https://www.coursera.org/specializations/discrete-mathematic...

Highly agree. As a current high school student, I've gone out of my way to study discrete math. Though I found calculus interesting, it's not particularly applicable to any part of CS except for a few concepts. OTOH, DM is incredibly useful for practically everything, which is what led me to seek it out.

if your interests tend toward machine learning, you may run into calculus again. in particular, if you keep going past the "train a neural network" phase (for which very basic calculus is fine) to the optimization problems that are under the hood of most ML algorithms, you wind up in the land of functional analysis.

> Discrete math shows up on most middle and high school math contests.

That seems a terribly weak reason for anything to be important.

When funding for your school is based off of test scores in a horrible way this is what we get.

My daughter is in 6th Grade and she has no Science or Social Studies this year. Reason: She has her Math and Science testing this year.

When did science become the enemy of math?

Math contests are not related to standardized testing. The contests are entirely extra-curricular, and probably mostly benefit those kids who have exhausted their school's standard curriculum.

I understand that BUT school administration is looking at Math contest through standardized testing outcomes.

My peev has been, how do I improve my problem solving skills, not necessarily Mathematics wise. But in general.

Read _How to Solve It_ by Polya

Bought it just now.

I literally just stopped working on my discreet math homework tonight before loading HN and seeing this article.

Reply on news.ycombinator.com