10 ms·
Abstract Algebra (2016) [pdf]
- adenadel 10y agoThis was the book we used for my abstract algebra course. Robert Beezer also has an open linear algebra textbook http://linear.ups.edu/ http://linear.ups.edu/
- hackernewsacct 10y agoBesides crypto. What applications does Abstract Algebra have in CS?
- dkarapetyan 10y agoMonoids, groups, rings, fields, etc. are all very relevant to cryptography. In general algebraic constructions come up more often than you might think. The idea of a homomorphism though not specific to algebra is prevalent in almost any formal domain. Compilers by and large can be considered homomorphisms that preserve certain semantic properties which if you dig deep enough can be expressed as algebraic structures: http://www.logicmatters.net/resources/pdfs/Galois.pdf http://www.logicmatters.net/resources/pdfs/Galois.pdf. Developing an intuition for all those things is best accomplished by studying abstract algebra.
- dualogy 10y agoThanks for the link, the whole site (logicmatters.net) seems awesome, aka for me worth bookmarking for future study!
- Smaug123 10y agoSmith is a great expositor. I had the joy of participating in a category theory reading group with him; he really knows his stuff. It's refreshing to be taught by a mathematician/philosopher rather than simply a mathematician.
- jinfiesto 10y agoMonoids aren't just relevant to cryptography. Any structure with an associative "+" operator forms a monoid (technically semi-group, but whatevs.) Lists are a prime example.
- Bahamut 10y agoCategory theory is considered a field that is associated with algebraic skillsets. Edit: Crypography is specifically associated with algebraic number theory. Abstract algebra is also used in algebraic geometry, which also comes into play with facial recognition software, and maybe with fingerprinting as well.
- hackernewsacct 10y agoEvery reply to my parent question has been excellent. What beginner resources do you recommend for learning category theory and its applications to programming?
- mathgenius 10y agoI'm not sure there is any good resources for CT applied to CS. But anyway, check this out: http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of-algebraic-data-types-part-iii/ http://chris-taylor.github.io/blog/2013/02/13/the-algebra-of... There's alot of category theory implicit in these ideas. You can learn the abstract approach later on, after you have seen a bunch of examples.
- tomku 10y agohttps://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ https://bartoszmilewski.com/2014/10/28/category-theory-for-p...
- ooqr 10y agoI'd suggest learning it via Haskell or maybe Scala if you've found programming helps your understanding of mathematics as I have. Learning via doing, internalizing by example, then diving deeper into the then-easier theory is how I like to go about things.
- deleted 10y ago[deleted]
- posterboy 10y agothe book in the article you are posting under, perhaps. just a hunch :)
- AnimalMuppet 10y agoInteger arithmetic in hardware (and many languages) is a ring. If I understand correctly, groups are the basis of some error correction codes. Monads are used for many things in functional programming.
- umanwizard 10y agoDo you mean to say a finite ring? "Pure" integer arithmetic in math (without any notion of overflow or wrapping) is a ring also, so I'm not sure what distinction you're making by saying "in hardware".
- AnimalMuppet 10y agoYes, a finite ring. There are languages that overflow from hardware integers into some kind of BigNum automatically. Those languages are not finite rings. (Well, OK, they're finite in the sense that eventually the memory space will be exhausted...)
- umanwizard 10y agoyep, but they're still rings :)
- Ixiaus 10y agoIt has a lot of application in functional programming languages, thinking of my programs algebraically has had a meaningful effect on what feels like "clearer expression of thought" in my code.
- swordswinger12 10y agoMost of the modern theory of error-correcting codes has its roots in abstract algebra. It's also important in theory - Babai's recent celebrated quasipolynomial algorithm for graph isomorphism relies on group theory. Most of the recent results in cryptographic obfuscation also rely on group theory because they encode circuits as permutation matrices using Barrington's theorem.
- adenadel 10y agoSome of the applications mentioned in this book are: -cryptography -algebraic coding theory -Burnside's lemma -molecular symmetry -design of software for parallel processors -lattices and Boolean algebras applied to logic, circuit theory, and probability -Galois theory
- catnaroek 10y agoAs Stepanov said: “[Generic] algorithms are defined on algebraic structures”. He even gives an example: “I realized that a parallel reduction algorithm is associated with a semigroup structure type”. If you care about algorithms being maximally reusable (as in “just reuse”, rather than “tweak and reuse”), you definitely want to adopt an abstract-algebraic mindset. Source: http://www.stlport.org/resources/StepanovUSA.html http://www.stlport.org/resources/StepanovUSA.html
- Drup 10y agoI would tend to say: It's the basis of everything. Here are some examples that were not given in other comments: - Graph theory is pretty algebra-heavy, and graphs are everywhere. - Static analysis, in particular abstract interpretation, relies heavily on vector spaces and various algebraic structures. - All the "highly functional" structures (you know, monads and the like) are an off-shot branch of algebra. - Patch theory (git, darcs and other versioning systems that rely on patches). You get nice stuff if you use algebraic properties (such as having your patch commutes and things like that).
- jinfiesto 10y agoTo extend the "functional structures" comment, monoids are literally everywhere in software.
- cpsempek 10y agoI don't know about very specific applications, but I think the field itself and is very complimentary to CS, especially when considering finite or discrete structures. As it's name suggests, abstract algebra abstracts "nice" properties of, e.g., integers and formalizes them in a very concise and general manner. Modern abstract algebra is deeply tied to category theory, and so now these "nice" properties get abstracted even further out to maps between objects, and as maps between categories (i.e., functors). As such abstract algebra is tied to functional programming on some level (I know nothing about this connection though). Linear algebra is a subfield of abstract algebra, and lots of general theorems about what classes of matrices are diagonalizable, or what their eigenvalues look like, etc. are within the purview of abstract algebra. These types of results are relevant to many algorithms, e.g., page rank. Aside from that, I think abstract algebra is quite a beautiful field in its own right. Two books I would recommend are Artin's Abstract Algebra (as an intro) and Lang's Algebra (more advanced, good bridge into the category theory perspective).
- semigroupoid 10y agoI second the recommendation for Artin's Algebra. I'd also recommend Paolo Aluffi's Algebra: Chapter 0, which is a nice alternative to Lang and also uses category theory right from the beginning and doesn't require many prerequisites. [0] https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathematics/dp/0821847813/ https://www.amazon.com/Algebra-Chapter-Graduate-Studies-Math...
- axlprose 10y agoOne way to view it, is that all other fields with the word "algebra" in them, are applications of Abstract Algebra. That includes Linear Algebra, Relational Algebra, and Boolean Algebra, which you might already be familiar with and know their relevance to CS.
- imh 10y agoFollowup question: Are there good applied books that cover examples in broader fields than just crypto and coding theory?
- platform 10y agoabstract algebra is foundation for a) arithmetic as applied to 'Classes'. Eg overloading arithmetic operators that work on custom classes -- is, in a way, what abstract algebra does . b) Interval arithmetic. For example alen algebra applied to arithmetic of time intervals c) relational database theory as relates to various ways to construct functions on relations. d) type theory (see https://homotopytypetheory.org/book/ https://homotopytypetheory.org/book/ ) e) combinatorics and linear programming (basically being able to express recursive and generative constructs, and reason about them).
- Smaug123 10y agoThough note that HoTT is not the only approach to type theory; there are many others.
- chas 10y agoI think that Abstract Algebra has the same relationship with CS as Linear Algebra has with the theory of most engineering disciplines. That is to say that in computer science, Abstract Algebra is the natural setting to define and decompose problems and design their solutions. For a specific example, CRDTs are a fundamentally algebraic approach to problem solving in computer science. They were discussed recently on HN here. [0] If you want to go further down that rabbit hole, Joseph Goguen spent a large portion of his career working on applications of Abstract Algebra to computer science. He produced a category-theory-focused introduction here. [1] [0] https://news.ycombinator.com/item?id=13803843 https://news.ycombinator.com/item?id=13803843 [1] https://www.cs.ox.ac.uk/files/3395/PRG72.pdf https://www.cs.ox.ac.uk/files/3395/PRG72.pdf
- tptacek 10y agoCrypto is probably a better way to learn abstract algebra than the other way around, for whatever that's worth. You don't need more than a surface level understanding of abstract algebra to do fairly serious crypto work, but a lot of abstract algebra made more sense to me after a few years of crypto.
- madhadron 10y agoOff the topic of my head, pretty much everything to know about consistency in distributed systems boils down to semilattices.
- EdwardCoffin 10y agoGuy Steele [1] sometimes mentions it. He gave an interesting Google Tech Talk called Four Solutions to a Trivial Problem [2], and at 1:59 [3] he said: Also, algebraic properties are important. I've got a background in applied algebra, and I think that has informed my programming. And I think that making programmers aware of algebraic properties of their code, and communicating some of those properties to the compiler, may be worthwhile. The language Fortress [4], which he was one of the language designers of, allowed one to explicitly provide the compiler with such information - you could say that a certain operation was distributive or associative for instance, and the compiler could then do some refactorings and optimizations taking this knowledge into account. [1] https://en.wikipedia.org/wiki/Guy_L._Steele_Jr https://en.wikipedia.org/wiki/Guy_L._Steele_Jr. [2] https://youtu.be/ftcIcn8AmSY https://youtu.be/ftcIcn8AmSY [3] https://youtu.be/ftcIcn8AmSY?t=1m59s https://youtu.be/ftcIcn8AmSY?t=1m59s [4] https://en.wikipedia.org/wiki/Fortress_(programming_language) https://en.wikipedia.org/wiki/Fortress_(programming_language...
- FullyFunctional 10y agoGHC Haskell (not standard Haskell) supports this and it's heavily used. Look for "Rewrite rules".
- qntty 10y agoIf you want to learn abstract algebra for the first time and you're anything like me, don't just read a book about it. It'll start to sound like a bunch of abstract nonsense. Eventually you'll have the skills needed to "bring it alive" for yourself with a set of concrete examples that you'll learn to refer to again and again. I would recommend starting by watching some lectures about it (you can find some here [1] under the lecture schedule). [1] https://www.math.upenn.edu/~ted/371F14/math371.html https://www.math.upenn.edu/~ted/371F14/math371.html
- j2kun 10y agoHaving a set of concrete examples in mathematics is like unit testing in software. The second you get stuck on a theorem, you fall back on your examples. The second you run out of examples that explain a behavior or new theorem, you write down new examples.
- pizza 10y agoAgreed. Google images is a surprisingly decent source of visual examples for intuition building/testing, although the signal-noise ratio is a crapshoot.
- westoncb 10y agoI don't see how a lecture would improve things over a book (assuming you still can't ask questions), though it does of course depend on the book. I'd just pick up Pinter's 'Abstract Algebra'—lots of good concrete examples, one of most readable math texts (in any subject) I've come across. Edit: also, there's a Dover edition you can get for < $15.
- eriknstr 10y agoExperienced lecturers might have insights into what kinds of difficulties students typically experience with the material, leading them to organize their lecture in a way that is different from a book. Then again, experienced lecturers might also write books as well where they consider the same things for their book.
- haldean 10y agoFor those who prefer dead trees, the hardcover is miraculously inexpensive: https://www.amazon.com/Abstract-Algebra-Applications-Thomas-Judson/dp/1944325026 https://www.amazon.com/Abstract-Algebra-Applications-Thomas-...
- rckrd 10y agoFor self study of abstract algebra, I recommend Dummit & Foote. I used it as a supplement to my undergrad algebra classes and found it to be very useful. This is in contrast to some books like Artin which leave a lot to the readers, while not necessarily bad, are sometimes difficult for self-study. [0] https://www.amazon.com/Abstract-Algebra-3rd-David-Dummit/dp/0471433349/ref=pd_sim_14_4?_encoding=UTF8&pd_rd_i=0471433349&pd_rd_r=00BFEVST8PPDFE5YR12G&pd_rd_w=pNsRA&pd_rd_wg=9P8LG&psc=1&refRID=00BFEVST8PPDFE5YR12G https://www.amazon.com/Abstract-Algebra-3rd-David-Dummit/dp/...
- dkarapetyan 10y agoI've learned from both in various undergrad and grad courses and I have to say I like Artin better. Dummit & Foote is a little too dry. I recommend Artin and Dummit & Foote as a supplement.
- trentmb 10y ago> For self study of abstract algebra, I recommend Dummit & Foote. I used it as a supplement to my undergrad algebra classes and found it to be very useful. Because you used it as a supplement.
- egonschiele 10y agoSince everyone is pitching their favorite books on abstract algebra, here's mine: http://a.co/fg0OUdG http://a.co/fg0OUdG. I'd love to hear what differentiates this book. Why should I read this one instead of the existing options? Is it because Sage is used?
- javajosh 10y agoWhen I was a physics major at UCI the abstract algebra course ended up being my favorite course. The prof was young, and a real hard ass. Apart from the usual, he forced us to memorize proofs and regurgitate them for tests, as well as come up with original proofs. That might sound draconian (it certainly did to me; none of my real analysis classes asked that of us) but it turned out to be really hard to do unless you understood the entire proof. And it also turns out that if you understand a proof, or a set of them, you can produce new ones. Of course, almost everyone failed the course. One guy got an A, a couple of us got C's (I was one) and the rest got F's. Never been prouder of a C in my life.
- Smaug123 10y agoYour analysis exams didn't require bookwork? For someone who has done four years of maths at Cambridge, this idea is dumbfounding: about a third of each exam was bookwork. (Except, in my year, Category Theory, in which there was no bookwork at all. Of course I don't hold a grudge about how much time I spent learning the proofs of the monadicity- and adjoint-functor theorems.)
- javajosh 10y agoNot sure what you mean by "bookwork". Is that what memorizing proofs is called in the UK? Most of the exams and homework were more typical math exercises, e.g. little proofs and calculations within the context of special cases. I mean, I remember getting tested on parts of the "epsilon delta" definition of a limit in analysis, for example, but I don't recall ever being asked to regurgitate the entire thing correctly. It's funny but I don't even associate important tools like Taylor series with "proofs", only applications. The lecturer would sometimes prove things, but we were never tested on the proof, only the ability to apply the result. Mind you, I was physics not math so perhaps that's the difference. In fairness there is a LOT of math tools to learn, and I'm not sure there's really time to get into proving everything as an undergrad, but perhaps that's a mistake.
- Smaug123 10y agoWiktionary's definition of "bookwork" is accurate: "The act of memorising information; used attributively to describe or denote questions that test information learned rather than requiring additional thought." It notes that the definition is "chiefly University of Cambridge", which I didn't realise. Perhaps it is indeed a physics/maths thing.
- Koshkin 10y agoI can recommend an inexpensive little book by Pinter, which is one of the most student-friendly abstract algebra books on the market.
- techwizrd 10y agoWhen I took Abstract Algebra as part of my Math degree, we used Gallian, Herstein, and Judson. Gallian had a lot of examples and felt very much like the textbooks I used in high schools (colorful, lots of prose, etc.) It is incredibly easy to get into, but sometimes you've understood something and you don't need 25 more examples. Herstein and Judson were both a less verbose (sometimes to the point of being unhelpful), but I'd still recommend them. I think I learned a lot from being exposed to different books. I could always look at another book if one book's explanations, examples, proofs, exercises were an issue. The Math Stackexchange was also invaluable because many of the proofs I saw there were very different from the ones I saw in class or in textbooks.
- lancefisher 10y agoGallian's Contemporary Abstract Algebra is the book I used. I really loved the subject. I had an awesome teacher that did a lot to inspire, but this was a good book. https://www.amazon.com/Contemporary-Abstract-Algebra-Joseph-Gallian/dp/0618122141 https://www.amazon.com/Contemporary-Abstract-Algebra-Joseph-...
- lancefisher 10y agoThat's the 5th edition for $18. The 7th edition is $180!
- throwaway729 10y agoSo buy the 5th edition. One of the perks of being able to self learn is that these sorts of revenue models don't impact you :-) Edit: I've used Gallian. Not sure what's in the 7th edition but the 5th is perfectly good.
- __jal 10y agoIf it is like other edition changes, you can expect about four typo-fixes, a new sticker on the shrink wrap, a 7-10% price increase, and a single-use code for online tools that make the professor's life easier. Every third edition, a "new and expanded" final chapter and an intro change, and a 20% price bump. I used to date a textbook marketing manager. It was a joke internally, too.
- partycoder 10y agoWhile great, I hope there was an interactive version, like Jupyter notebooks. Jupyter can embed Sage.
- adenadel 10y agoNot sure why you're being downvoted. There is an online version with Sage code http://abstract.pugetsound.edu/aata/ http://abstract.pugetsound.edu/aata/
- partycoder 10y agoThanks, that's exactly what I was looking for.
- crb002 10y agoThe lack of transformation semigroup coverage astounds me. Most interesting endofunctions are not permutations.
- anajuoh 10y agoI remember when the first version of this text came out. It was tested out on myself and two other students in Beezer's class. It's a solid text.
- mavam 10y agoHere's my very basic attempt to visualize some of the key structures: https://github.com/mavam/abstract-algebra-cheatsheet https://github.com/mavam/abstract-algebra-cheatsheet. Is anyone aware of something similar, but much more comprehensive?
- Chinjut 10y agoOne slight correction: for Field, the commutative group structure of multiplication should be on S\{0}, not on all of S.
- snakeboy 10y agoI've almost-exclusively seen "Commutative Groups" referred to as "Abelian Groups". Is there a reason you use "Commutative Groups"? I'll admit my algebra is quite limited and I may be missing a subtlety.
- gizmo686 10y agoThere is no subtlety here. That groups which are commutative are referred to as "abelian" is purely historical. Refering to them as commutative helps understanding for people who are not fammillar with them, and helps highlight the structural simmilarity that the diagram is attempting to show. Sadly, I find it unlikely that we will get mathamaticians to agree to stop calling them Abelian groups, so learners will have to learn that name eventually.
- godd2 10y agoThat's why I always call it partition sort instead of quicksort.
- deleted 10y ago[deleted]
- bokumo 10y agoThe linked PDF also has an online version which is superior in many ways because it has inline executable Sage examples. It can be found at: http://abstract.pugetsound.edu/aata/ http://abstract.pugetsound.edu/aata/ Also, this textbook is one of several open source textbooks developed using MathBook XML which allows authors to create multiple output formats such as PDF, HTML and ePub from one canonical source document written in XML. If you are interested in learning about MathBook XML you should check out: http://mathbook.pugetsound.edu/ http://mathbook.pugetsound.edu/
- globuous 10y agoEvariste Galois always intrigued me. He died aged 20 in a duel supposably for some love story, yet he apparently had "time" to lay the foundations of some pretty serious math. To quote the into from the last chapter of this book which introduces Galois Theory: "[...] attempts to solve the general fifth-degree, or quintic, polynomial were repulsed for the next three hundred years [...] no solution like the quadratic formula was found for the general quintic [...] Finally, at the beginning of the nineteenth century, Ruffini and Abel both found quintics that could not be solved with any formula. It was Galois, however, who provided the full explanation by showing which polynomials could and could not be solved by formulas. He discovered the connection between groups and field extensions. Galois theory demonstrates the strong interdependence of group and field theory, and has had far-reaching implications beyond its original purpose." My mom was actually reading a novel about him (a beautiful mind kinda style) last summer. I wonder how he would have turned out if he had not passed away so young. Surprisingly, the only other mathematician that died really young (aka younger than jim morrison and co) is Niels Henrik Abel, also mentioned in the quote. Makes you wonder how healthy algebra is, doesn't it ;p
- jsolson 10y ago"The tragedy of Galois is that he could have contributed so much more to mathematics if he'd only spent more time on his marksmanship" - Olin Shivers, supposedly quoting his PhD advisor
- kdazzle 10y agooh no way! Whuddup loggers. I was there in 2005.
- dominotw 10y agoI took Abstract Algebra course at a local university couple of yrs ago. I learnt how to do proofs first from Spivak's calculus, learning to do proofs felt very similar to writing code. I really enjoyed doing Abstract Algebra proofs. Got top score in the course and promptly forgot everything about it after a couple of months. Back to the day job fixing garbage collection on poorly written java apps.