What is it about
And how is it possible to make up the required material of the first courses of the university in the fourth ten and with an aversion to algebra?
To the madness of the brave we sing a song!
The target audience of the Guidebook is those who are suddenly interested in mathematics or feel the need to increase their professional effectiveness, but for some reason they are not able to devote several years of their lives to academic education. If you have a need to understand, but fundamental knowledge is sorely lacking, and you feel like a foreigner in a country of mathematics, where they speak an incomprehensible language, try to go this way as a tourist. The entire route is a sightseeing tour and is designed for several days, a maximum of two weeks. For comparison: a full academic course is about five years. The ultimate goal of the proposed route is to get acquainted with the principles of one highly specialized section - elliptical cryptography. However, it is not necessary to go to the end if this section lies outside the scope of your interests or if you are faced with serious difficulties or dangers. But, since you picked up the Guide, still try to get to at least the end of the section “Formula Language”.
Like a dictionary, this guide can also be used for reverse translation. Perhaps it will be useful to mathematicians who are forced to contact and work closely with non-mathematicians, constantly overcoming the gap of misunderstanding. This case seems so difficult that the line of Maxim Gorky in the epigraph is a universal answer to both sides. In any case, I hope for feedback and try to replenish our knowledge about why they do not understand us, and how this can be fixed.
And now, knowing that there are no royal roads here, we will try to pave at least a tourist path.
Formula Language
I was told that each formula included in the book will halve the number of customers. Then I decided to do without formulas at all. True, in the end I still wrote one equation - the famous Einstein equation E = mc ^ 2. I hope it doesn’t scare away half of my potential readers.
Stephen Hawking - A Brief History of Time
If Hawking’s publisher is right, then adding just 33 formulas is enough to make the number of potential readers close to zero. Will we try?
First of all, it is necessary to achieve a sufficient level of understanding of the notation. Remember, math is a language.
In a first approximation, several layers of understanding of a mathematical text can be distinguished. The first layer is the selection of lexemes, the so-called lexical analysis. The second is the construction of expressions and other semantic constructions. Programmers call this the word parsing, that is, parsing, and general mathematicians usually do not call it at all, since they use this mechanism subconsciously. Next are the layers responsible for understanding the subject area, physical meaning and all that.
Some mathematicians see programmers as non-mathematicians. This is unfair. Firstly, programmers have to deal with a machine that does not forgive the omissions in the text of the programs. Compare with a typical scientific article, where the expressions “obvious”, “easy to show”, “no brainer”, etc. are often used, but in fact the transitions are not deeply obvious. Therefore, thanks to programming, a whole branch of mathematics was born devoted to formal languages and their analysis. Secondly, in harsh conditions, the programming languages themselves and related tools have evolved. See how elegantly modern languages solve the problem of matching variables to objects. A serious problem, by the way, is not to get confused in the notation when there are too many of them, and they come from different sources. And if you spend a little time on a quick overview of such specific languages as Coq, Agda, Idris, you will see the closest connection between mathematics proper and programming.
Lexical analysis
I used to know how letters are written, I believed in the power of words.
Crematorium - Last Chance
First, ask a friend programmer what a lexer and parser are. You don’t need to go deep, just understand by examples what a token is. If you hear strange words like “el-er-parser” or “syntax tree”, quietly leave the room. Most likely, you already have enough, the programmer is no longer needed. Digest your knowledge. Then you need to learn how to distinguish tokens in real mathematical texts. Practice on randomly downloaded articles. Avoid documents in formats other than pdf, as well as texts laid out immediately on web pages. However, there are sites about which it is reliably known that they can correctly display mathematical texts (Wikipedia and Habr are included in the white list). Paper books are also generally suitable. Do not try to extract meaning from the texts found, just train to parse formulas.
Letters
- The letters of two alphabets are usually used - Latin and Greek, but Cyrillic and Hebrew letters are sometimes found. It happens that the letters of different alphabets coincide in style. On the letter, this does not cause problems, since two different letters with the same type are not used in the same text. However, you may encounter the mockery of mathematicians if, for example, you read B aloud as “be” when you mean “beta”. Be psychologically prepared for this, you have to endure.
- Uppercase and lowercase letters represent different objects. (To some, this seems too obvious, but I consider it necessary to pronounce it explicitly. Once I needed to present the essence of my work to my colleagues from the patent department. When I almost reached the character of the anecdote “dad, where is the sea?”, I suddenly realized that the girls consider my designations m and M to refer to the same object. As soon as the misunderstanding was cleared up, the whole process, thanks to their professionalism in their work, quickly and decisively ended in complete success.)
- The same letter, written in different fonts, means different objects.
As a rule (in algebra), one letter is an independent token. If several letters are written in a row, then multiplication is implied. For example, abc means the product of a, b, and c. However, there are exceptions. First of all, this is the name of many standard functions and other notation, which is a multi-letter token: etc. They are usually represented by a straight roman, unlike other letter tokens, which are written in italics. In addition, in computer science and in some other areas, they depart from this rule, where a sequence of letters denotes a single word-token. If in a particular case there is even the slightest doubt, consult a specialist.
Parentheses
The most important role in terms of parsing is played by parentheses. You probably already know or guess that parentheses are used to group tokens. But there are exceptions. If the formula seems strange to you and contains extra pairs of brackets, or even the balance of the brackets is broken, most likely you come across an example with an alternative use of brackets. Go to a specialist for clarification.
Indices
Pay attention to the top and bottom indices. This is what typography looks like superscript and subscript. The superscript is simpler: as a rule, it stands for exponentiation. With the bottom a little harder. It can be understood in two ways:
- Like a mapping operation. For example, Is such a function which takes as an argument . If now this point is incomprehensible, it's okay, this place can be skipped for now.
- As a way to form a new token when convenient letters are already over. It can often be assumed that - these are just three different objects.
At some point, it may seem to you that both of these points are essentially the same thing. Do not worry, this is normal, you have become a little closer to enlightenment. Schedule a meeting with a specialist.
Other characters
Mathematicians are aesthetes. They love when not only content but also form is beautiful. They are pleased when the formulas are typed in good, suitable typography. Knut made a delicious gingerbread called . Take a tutorial on typing and typesetting formulas and find the symbol tables there. Now it’s important for you how these symbols are classified: letters, operators, relationship signs, arrows ... Without delving into the mathematical meaning of symbols, try to understand how the symbols of each class are syntactically used. For example, there is a class of binary operations for which right and left equidistant from the operation symbol should be some kind of subexpression.
Figures
Non-mathematicians believe that mathematicians believe. In fact, mathematicians are rarely considered, and numbers are mainly used for numbering objects. Apparently, therefore, the "Numbers" section was added in a hurry and illogically follows the "Other Symbols" section. You yourself can tell experts how digital tokens are formed and what they mean.
Notation Conventions
Let a, b, c, d, e, f be real numbers, where e is not necessarily equal to the base of the natural logarithms, although it may coincide with it.
In mathematics, there are conventions about which characters to use in what cases. However, in different sections these agreements may vary. It is like dialects of a language. There are notations standardized in all mathematics. Check out the conventions that are accepted in your subject area. In addition, some scholars are negligent and sometimes violate generally accepted agreements. Unfortunately, in most cases there are no sets of rules on this subject, you can discuss this with your specialist on occasion.
Although mathematics is generally supranational, there are cultural differences. You may encounter them if you deviate too far from the route suggested by the Guide. For example, the English and Russian designations of tangent, cotangent, hyperbolic functions are distinguished. Also, the same letters can be pronounced differently depending on cultural traditions. To save effort, learn the English names of all letters, including Greek. If you have not skipped school, then at least there will be no problems with the Latin alphabet. If you use them in Russian, your interlocutors may frown, but this time they will have to endure. If you want to make them happy, learn the names of Latin and Greek letters accepted in the Russian-speaking mathematical culture.
Parsing
Expressions
You, most likely, have heard the term “tree” not in the botanical, but in the mathematical sense. This is a fairly simple thing, if necessary, refresh your knowledge. So, a mathematical expression has a tree structure. This means that the expression consists of subexpressions that consist of subexpressions ... But this process is not endless, but ends with some subexpressions consisting of tokens.
Some tokens themselves are elementary expressions. For example, numbers (more precisely, numeric literals) and variables. And some require that arguments be added to them in certain positions, that is, some kind of subexpression. Then they form a larger expression. For example, the symbol of an addition operation requires expressions to the right and left of it. We can say that the lexeme has some arity or, if you prefer chemistry, valency, is how many and in what places you need to add to the lexeme of subexpressions to form an expression. For operation + arity can be described as follows:
By the way, here you see an example of how mathematical notation serves to describe mathematical notation - the dot symbol serves to mark the place where you want to write the argument.
This entry exactly means that the + token requires arguments to the left and right of it. Different tokens require a different number of arguments, in addition, the location of the arguments is not limited to “right” and “left”, but can be, for example, “top”, “bottom”, “right-bottom”. There are also compound tokens that have existed since ancient times, but mixfixes got a special name as programming languages developed. For example, a scalar product of vectors is denoted as follows: .
Sometimes tokens conflict because they cannot decide who owns the argument written between them. Then you have to add brackets.
Variables
Some tokens have a meaning that has been attributed to them from above - either somewhere higher in the text, or by links in other texts. Or the meaning is implied as generally accepted in a given discipline or in all mathematics. For example, the plus symbol denotes an addition operation. Plus - he is in Africa plus. However, perhaps somewhere closer to the end of your route you will come across a plus symbol with some unusual meaning. There are still tokens (usually alphabetic) that are not explicitly indicated by anything, they are called variables, of which there are several types.
- Parameter. This is a variable about which it is said that it is signified by something, but it is not said what exactly. If it seemed strange to you, you can skip it for now, and when you meet the parameters, you will immediately understand everything with examples.
- Free variable. If a variable is found in the expression about which nothing is said, then such a variable is called free. Strictly speaking, nothing can be said at all. You have the right to ask the author of the formula from which set the free variable in it is taken. Feel free to ask, this is useful: even if the explanations turn out to be incomprehensible, they will take you a little more seriously.
- The bound variable. If you don't like the libertine of free variables, there are several ways to limit their freedom. You can add something to the expression, so you get a new expression in which the previously free variable is locked. And the new expression, unlike the old one, will no longer depend on this variable. If you are curious about what this “something” is, go look at the quantifiers or at a certain integral. Try to look only at the syntax, not delving into the meaning, but, you know, addictive.
Context
It happens that, looking at the formula, it is impossible to distinguish a free variable from a parameter. This means that additional information needs to be taken from the context, which is usually expressed by other formulas or text in human language. Depending on the context, the formula may have different meanings. If you need to understand the formula, always study the context and seek understanding.
However, formulas can exist without context, just as a syntactic object on which transformations can be made. Mathematicians can often first generalize - “forget” the context, then make calculations, then “remember” the context and re-understand the meaning of the formulas obtained.
One interpretation of quantum mechanics requires that the context of physical meaning be discarded. It’s called “shut up and count”.
Equals symbol
The equal sign is very important. It is used in different ways, and you need to be able to distinguish between them.
- Valuation of a variable by value. This is when the variable is on the left and the expression is on the right. In some disciplines, in such cases, instead of = they write: = or even :: =.
- Identity. On the left and on the right are some expressions, and the person who writes this claims that both expressions are equal. The symbol is also used here. . Have you thought about what “equal” means? It is worth discussing, but it may take you far from the route.
- The equation. This is a way of describing fundamentally new entities. Mathematicians do it this way: they take several free variables, build expressions over them and drive them into an equation or even into a system of several equations, so that they are even closer. And then they watch how these unfortunate variables rush about in constraints, forming bizarre sets. And then they study these sets with great interest. (By the way, your route passes through the territory of set theory, you have to get to know them better.) To describe the resulting set is to solve the equation. Children at school are usually given equations that give rise to very simple sets of one element, sometimes two or none. But adult scientists in this matter are big entertainers. And some physicists are able to generate the whole universe with one equation.
Extracting meaning from formulas
Something is written, but in parentheses it is. They tried - and really, OH.
The brain of a mathematician in physical characteristics does not fundamentally differ from the brain of a typical representative of the intellectual majority. Even in terms of memory and computational speed, the difference is not so great. How do mathematicians manage to understand cumbersome formulas and understand them?
Part of the answer lies in the ability to single out the main thing, and abstract from the unimportant. As you remember, an expression consists of subexpressions. When you see a big and scary expression, do not rush to look at all the subexpressions at once, opening all the boxes, boxes, boxes and boxes. You must first understand the context: if you have an equation, is it necessary to solve it or just classify it. And if you decide, then straightforwardly or later, analytically or numerically. It happens that you need to trace the occurrence of a single variable, then all the subexpressions where it does not enter are just constants that, although difficult to look at, are not a fact that require your attention.
As you can see, mathematicians sometimes themselves do not fully understand the meaning contained in the formulas. But this does not prevent them from making transformations and making correct judgments.
When you see a formula, try to make some judgments about it, as little as possible going into details. Try to classify it. Of course, at first, almost all formulas will fall into the class “some strange bullshit”, but gradually you will learn more and more classes: “large number”, “polynomial”, “linear equation”, “ellipse equation in polar coordinates”, etc. .d.
Psychological aspects
The rotor of the field, like a divergence, graduates itself along the back and there, inside, turns the matter of the matter into spiritual electric vortices, from which the synecdo of answer arises ...
Arkady and Boris Strugatsky - The Tale of the Three
That is, the XOR in the multiplicative group of points on the curve will be multiplication by a scalar, in fact?
Since you often have to contact specialists, be prepared to endure ridicule and even humiliation on their part. Tune in to this in advance and consider it a fair payment for the knowledge gained.
Gradually, your speech will seem to experts more meaningful, and, with due diligence on your part, they will begin to take you seriously. They value in the interlocutor not so much knowledge as the discipline of thinking. If you manage, as described above, to structure your thinking, then they may begin to communicate with you on an equal footing, despite the significant difference in actual knowledge.
Although mathematics as a whole is a gender-neutral discipline, lady syndrome in the from field may appear in this case. If your gender is female, then most likely the problem described in this section will affect you to a lesser extent. However, do not flatter yourself, do not neglect psychological preparation.
Despite everything, do not hesitate to share your difficulties with specialists. If your psychotype is Krosh (from Smeshariki), consider yourself lucky. If Losyash, Pin or Hedgehog, do not do nonsense, drop the Guide and go to study in an academic organization. In other cases, conduct additional psychological work on yourself, if necessary, contact specialists of the appropriate profile.
Guidebook beta testers commented that not everyone knows Smesharikov. I correct myself and give information on the mentioned psychotypes: Krosh is a sociable cheerful optimist, Losyash is a scientist and a popularizer of science, Pin is a mechanic, gloomy genius, Hedgehog is a young nerd.
Sections of mathematics
Mathematics is federated; your path runs through several of its cantons. The boundaries between them are laid at the whim of people, not nature, and therefore quite arbitrary. In fact, everything that exists is closely intertwined, and, as Vladimir Arnold said, mathematics is one.
If you are fond of trolling, try on the profile forum to jot down the thesis that such a concept applies or does not apply to such a section of mathematics. Or that such a discipline (hi, computer science) is or is not a branch of mathematics. Food generation is not guaranteed, but there are chances.
Arithmetic
There is only one trigonometric function - the exponent. And all sorts of sines and cosines are a perversion of the human mind.
A school teacher explaining the beauty of complex numbers to participants in a summer physics and mathematics school
This territory is familiar to you, passed in school. Check that you remember how to share with the remainder . If necessary, look in the textbook. Do not unnerve specialists.
Also remember the logarithm , you went through it. It will be needed in at least two places. First, on your route there will be a bit of information theory, only the base two logarithm will come in handy there. , . , , - , . « ». , . , . « ?».
, . . : a — , b — , , , . : , .
, , . , , . .
, .
Set theory
. «», « » « », . , , . , . , , . , , . , . . : . , — . . : ! ! - , , . — , .
- . . .
- . . , ? -.
- . , . -, , , .
- . . , - - .
- , « ». , . , . , .
- , . , . , , .
, , . . . . , , . , , ? , . , .
. . . , , .
,
,
-> -> -> . «» .
. , . , « » « » « », , , . , , : «», «», «» .., : «», «», «». , . -, , .
. «», «», «», «», «» .. «», «» .. , , «» « ». , , , . ? , , .
. . -, . -, , . , , ́ — , ́ , . , . , . , , . .
, , .
Logics
. , , , , , . modus ponens, , - .
— , . Take a look around. : , , , . , : . ! How do you like that?
, ( ), . dx , , - . - , .
, . - , ? It turns out, no. , , . . , .
- , , , , , . , , , . , , .
— , — . — . .
, , .
— , — . — ?
— , — . — — . , , , .
— -, — . — .
—
, , , .
- . . , . , . - , . , ( ) , . . , — , .
- . — . — . , . , . . ( !). , .
— , , . , . , , , .
Algebra
, , .
- —
. , , ( ) . , , . , . , , . .
. , . . , , , . , . . .
Attention! , . , . : , . Play with them, remember school rules like “the amount does not change from changing the terms of the terms” and justify the fact that these structures are really rings / fields. Explain why integers do not form a field.
Since the ultimate goal of this guide is precisely elliptical cryptography, you will have to familiarize yourself with the concept of a polynomial over a field . In order not to study the general definitions, contact a specialist so that he tells only what is relevant to the purpose of your trip.
If you like geometry more than algebra, you can go look at the elliptic curves above the field . But keep in mind that, despite the name, these visual objects are completely away from your path.
For the sake of interest, you can also meditate on the definitions of other algebraic structures: algebra (yes, algebra is such an algebraic structure; do not be alarmed, this is not recursion, but just homonymy), vector (linear) space ...
Return to the route. You are waiting for the final field . Read an article about them. Actually, not everything is needed. This is another case when to save effort it is better to immediately seek the advice of a specialist. Realize the classification of finite fields, it is simple. By the way, it will be interesting to know why the finite fields are also called Galois fields. Remember what you did in 20 years, and be ashamed.
If you like trolling, and you appreciate your abilities, try to recognize the bourbacists and anti-bourbacists at the thematic forum and pit them together.
Information theory
If you were born after 1970, then you were most likely told in high school about bits and bytes. Bytes in basic science are not particularly needed, but the concept of a bit needs to be known clearly. If necessary, look in the textbook.
Count or find out in the textbook how many total bit sequences of a given length exist. Play with the alphabet by encoding the letters in a sequence of bits. Think up or read in the textbook how to code integers. Consider what is useful in information theory is the logarithm of base two.
Probability theory
Anyone who has a weakness for arithmetic methods for obtaining random numbers is sinful beyond any doubt.
John von Neumann
Misunderstanding of probability theory and its application to practical issues is the most important source of human error. This is a very important topic, try to devote some time to familiarize yourself with its basics. Not necessarily right now, because for the ultimate goal of our route, only one of its applied subsections is enough - the generation of random numbers.
For now, it’s enough for you to realize that the issue of generating random numbers is very complicated, whole institutes have been dealing with it for decades. Even the definition of what is accident is very complicated. You can’t just take and take a random number. Unfortunately, there is a language trap that makes it difficult to understand the topic. The word random, as well as its Russian equivalent, “random”, although to a lesser extent, essentially means “horrible”, while for many applications, especially for cryptography, you need to choose far from random.
If it seemed to you that you understand the theory of probability well, see a specialist. If time permits, go away to look at the multi-world (Everett) interpretation of quantum mechanics. Do not get carried away, you are waiting at home.
Computability theory
Is it possible to make this compiler always warn that the program can go in cycles?
You will not need this section right now. It is simply useful to realize that not for any mathematically defined function there is an algorithm that calculates it. If you feel the strength in yourself, take an excursion through the history of the issue, try to understand the basic definitions and results. Do not overwork, this topic is optional.
Just to reduce your stress from the realization of your own ignorance, I will inform you that the question put out in the epigraph was asked to me by a respected professor of physics and mathematics, whose area of interest lay some distance from computer science. If you understand the anecdotal situation, your excursion was useful. Encourage yourself.
Complexity theory
Unfortunately, classical science has evolved so that the theory of complexity, strictly speaking, is based on the theory of limits from mathematical analysis. This is all because selfish mathematicians have not taken care of you. They approached complexity, already standing on the shoulders of the giants, and used the tools that they themselves possessed in perfection. For our humble goals, it was possible to build our own separate little theory of complexity, which even ultrafinitives would like. But, for example, I have neither the strength nor the motivation to finish building a fair piece of the landscape. Therefore, you still have to turn to what is called the word matan.
Mathematical analysis
I'm not a botan, I just love matan.
Read the definition of the sequence limit (you do not need a function limit). Replace all expressions like “such-and-such space” with “a set of real numbers”, mathematicians like to generalize, but you don’t need it. Make sure you can parse expressions that have a word . Most likely, you will have difficulties, this is normal. Believe me, the concept of limit is very intuitive, you only need to stimulate the corresponding part of your intuition. Ask a specialist to comment on the text of the definition. Draw graphics, play around with simple sequences. If time permits, go on an excursion to look at the second wonderful limit.
Even if you do not have a full understanding of the limit, you can immediately proceed to O-notation. You only need “O” big , but the load goes “O” small and all sorts of theta and omega. Do not overwork, for a start you just need to understand what they are . Find out, but rather try to guess for yourself why just a logarithm, not a logarithm for some reason. Then rest a bit and hold in your hands and . Look at (remember the context: here N is a variable, k is a parameter). Think about why they talk about polynomial growth when - just a monomial, that is, a special case of a polynomial, but they don’t put a lot of full-fledged polynomials under “O”. (Even if you do not speak Latin, you probably already guessed that a polynomial is the same as a polynomial, and a monomial is a monomial.) Hint: the reason is very similar to the one that “is simply a logarithm” and not “which logarithm to the ground. " Contact a specialist to clarify these issues. Learn to compare these "O" with each other.
Note: o-notation is a rare example when mathematical notation is not consistent. In recording the equal sign is used, while it implies something else, namely: “function belongs to class ". That is, an asymmetric sign should be used but that’s the tradition. Well, now you see that mathematicians are not sinless. Perhaps it will become a little easier for you to realize this fact.
Computational complexity theory - continued
Logarithm - a function, in principle, limited.
After a little insertion of the matan, you can easily master the scale for measuring asymptotic complexity. The complexity of the algorithms is usually measured in terms of their execution time: sometimes they talk about the usual time measured using the clock (well, when will this browser tab load?), Sometimes about the number of processor cycles or steps of an abstract computer. Those who are more inclined toward physics prefer to measure complexity in energy units, for example, in the amount of diesel fuel consumed for a Turing machine. All of these measurement methods are roughly equivalent. It is important to know how the elapsed time (or energy) depends on the size of the input data of the algorithm. This is N under “O” large in the asymptotic estimate and is the size of the input data, expressed in bits. Specialists agreed to believe that if the complexity of the algorithm grows no faster than a polynomial, then it is “easy”, otherwise “difficult”. It is appropriate here to go back a bit and remember how to compare functions with each other in terms of coolness, that is, in terms of the rate of asymptotic growth.
If you notice that the statement made in the epigraph is false, encourage yourself. He was delivered by a university teacher in computational methods. Knowing this context, think specifically what he meant.
One-way functions. Read the definition. Regardless of your level of understanding, discuss what you have read with a specialist. A good specialist can explain the basic idea on fingers, and how useful the one-way functions for cryptography are, and most importantly, it will not let you wander into dangerous territories.
If you have a question why one-way functions may even exist, stop. Take your time, think again. Think about your career, review your previous decisions. Maybe you should follow in the footsteps of Losyash?
Cryptography cryptography
Two absolutely identical black tracks narrowed into a colorless haze to the right and left at an angle of two-thirds of the pi. And across the right track was written in big white letters “For smart”, and across the left - “For not too much”. <...> The road for the smart was surprisingly short. <...> Behind the door was the same familiar room. In the familiar armchair, the familiar grandfather was snoring in all its wrappings, the familiar Murzil cat was lying on the familiar TV, the familiar blanket hung from the familiar bed.
Arkady and Boris Strugatsky - A Tale of Friendship and Unfriendliness
You have reached the foot of a peak called elliptical cryptography. Congratulations! Before the assault, take a break, get rid of the routine, plan the optimal time of day for you (for example, morning, if you are an early bird). Think again whether to go further. You have already received a valuable achievement and can more or less normally communicate with mathematicians on their topics in their language. Now is a good moment when you can return home without traumatic experience. The determination to go further has not left you? Good. And by the way, maybe Losyos is lonely without you?
Here, I would like to write “to be continued,” but, in accordance with the Pareto principle, this section would require 80% of the reader’s efforts, and would give only 20% of the benefit. And for the author it would be 80% of the work.
Acknowledgments
The author expresses gratitude to his present and former colleagues for the inspiration and statements that have replenished the citation fund. Special thanks to Shapelez habruiser for help in preparing the Guide.