Это база: Зачем нужна математика в повседневной жизни

1

Термин введен британским статистиком Дэвидом Кендаллом. Другое название – «пространство неряшливости» – используется специалистами по автоматическому распознаванию рукописного текста. – Прим. науч. ред.

2

Это математический термин. Свойство алгоритма дележа «свободный от зависти» означает, что каждый из участников дележа может быть уверенным в том, что никто не получил большую долю, чем он сам. (Разумеется, представления участников о величине и ценности долей могут быть разными.) – Прим. науч. ред.

3

Эрроу К. Дж. Коллективный выбор и индивидуальные ценности. – М.: ВШЭ, 2004.

4

Возможно, это справедливо для англоязычных публикаций, но на русском языке популярная книга В. Мудрова «Задача коммивояжера» вышла еще в 1969 году. – Прим. науч. ред.

5

Tommy Muggleton (перерисовка).

6

В школьных учебниках их чаще называют равными. – Прим. науч. ред.

7

В СССР первые компьютерные анимации движения животных появились даже раньше, до той эпохи, которую описывает автор. Так, мультфильм «Кошечка» был создан на машине БЭСМ-4 и перенесен на пленку на кафедре научной кинематографии МГУ в 1967 году. – Прим. науч. ред.

8

Jen Beatty. «The Radon Transform and the Mathematics of Medical Imaging» (2012). Honors Theses. Paper 646. https://digitalcommons.colby.edu/honorstheses/646.

9

Если смотреть на цены 2024 года, то вполне можно уложиться в $150 000, см. https://radio-med.ru/makers/kt/. – Прим. науч. ред.

10

Wikipedia.

11

Yi-Ping Ma.

12

G. G. Blasdel. «Orientation selectivity, preference, and continuity in monkey striate cortex». Journal of Neuroscience 12 (1992) 3139–3161.

1

В 2012 году аудиторская компания Deloitte провела исследование на тему «Измерение экономической пользы математических исследований в Великобритании». На тот момент научной деятельностью в сферах теоретической и прикладной математики, статистики и информатики занимались 2,8 млн человек. Суммарный вклад математических наук в экономику Великобритании (валовая добавленная стоимость) в том году составил £208 млрд – чуть меньше £250 млрд в ценах 2020 года, или около $300 млрд. Получается, что вклад 2,8 млн человек, то есть менее чем 10 % британского занятого населения, в экономику составил 16 %. Крупнейшими секторами были банковское дело, промышленные исследования и разработки, вычислительные услуги, аэрокосмическая отрасль, фармацевтика, архитектура и строительство. В качестве примеров в отчете названы, в частности, смартфоны, прогнозирование погоды, здравоохранение, кинематографические спецэффекты, улучшение спортивных показателей, национальная безопасность, борьба с эпидемиями, безопасность сетевых данных и повышение эффективности промышленного производства.

2

. http://www.maths.ed.ac.uk/~v1ranick/papers/wigner.pdf.

3

Сама формула выглядит так:

где x – значение случайной переменной, μ – среднее, а σ – среднеквадратичное отклонение.

4

Вито Вольтерра был математиком и физиком. В 1926 году за его дочерью ухаживал морской биолог Умберто Д'Анкона, и позже они поженились. Д'Анкона обнаружил, что во время Первой мировой войны доля хищной рыбы (акула, скат, рыба-меч), вылавливаемой рыбаками, повысилась несмотря на то, что в целом рыболовство захирело. Вольтерра создал на основе дифференциального исчисления простую модель того, как меняется со временем численность хищников и добычи, из которой следовало, что система переживает повторяющиеся циклы, где взлеты численности хищников чередуются с обвалами численности добычи. Главное, что в среднем численность хищников увеличивается пропорционально сильнее, чем численность добычи.

5

Несомненно, Ньютон пользовался также физической интуицией, и историки сообщают нам, что он, вероятно, позаимствовал идею у Роберта Гука, но ограниченность и узкая специализация еще никому не шли на пользу.

6

. www.theguardian.com/commentisfree/2014/oct/09/virginia-gerrymandering-voting-rights-act-black-voters.

7

Вопрос времени был не единственным. На Конституционном собрании 1787 года, которое привело к созданию системы с коллегией выборщиков, хотя называлась она тогда иначе, Джеймс Уилсон, Джеймс Мэдисон и другие считали, что наилучшим были бы прямые выборы. Однако существовали практические проблемы, связанные с определением того, кто должен получить право голоса, причем между северными и южными штатами по этому вопросу были серьезные разногласия.

8

В 1927 году Э. Кокс использовал эту же величину в палеонтологии для оценки округлости песчинок; это позволяет отличить песок, образовавшийся в результате выветривания, от песка, обкатанного водой, и определить условия окружающей среды в доисторические времена. См.: E. P. Cox. «A method of assigning numerical and percentage values to the degree of roundness of sand grains», The Journal of Paleontology 1 (1927) 179–183. В 1966 году Джозеф Шварцберг предложил использовать отношение периметра округа к длине окружности той же площади. Эта величина обратна корню квадратному из оценки Полсби – Поппера, так что она ранжирует округа точно так же, хотя и с другими числами. См.: J. E. Schwartzberg. «Reapportionment, gerrymanders, and the notion of 'compactness'», Minnesota Law Review 50 (1966) 443–452.

9

Заключив в окружность холм, то есть искривленную поверхность, она сумела втиснуть в свой круг еще большую площадь.

10

V. Blåsjö. «The isoperimetric problem», American Mathematical Monthly 112 (2005) 526–566.

11

Для окружности радиуса r

длина окружности (= периметру) = 2πr,

площадь круга = πr²,

периметр² = (2πr)² = 4π²r² = 4π(πr²) = 4π × площадь.

12

N. Stephanopoulos and E. McGhee. «Partisan gerrymandering and the efficiency gap», University of Chicago Law Review 82 (2015) 831–900.

13

M. Bernstein and M. Duchin. «A formula goes to court: Partisan gerrymandering and the efficiency gap», Notices of the American Mathematical Society 64 (2017) 1020–1024.

14

J. T. Barton. «Improving the efficiency gap», Math Horizons 26.1 (2018) 18–21.

15

В начале 1960-х годов Джон Селфридж и Джон Хортон Конвей независимо друг от друга нашли свободный от зависти метод дележа пирожного для трех игроков:

1) Алиса разрезает пирожное на три равноценных, по ее мнению, кусочка.

2) Боб пропускает ход, если не может выбрать среди трех кусочков самый большой; если может, он отрезает от самого большого кусочка лишнее, чтобы он перестал быть самым большим. Обрезки называются «остатком» и откладываются в сторону.

3) Чарли, Боб и Алиса, именно в таком порядке, выбирают для себя кусочек, который они считают самым большим или одним из самых больших. В том случае, когда Боб не пропускает ход 2, он обязан выбрать обрезанный кусочек, если Чарли не выбрал его первым.

4) Если Боб пропустил ход 2, то обрезков нет и дележ закончен. Если это не так, то либо Боб, либо Чарли взял обрезанный кусочек. Мы можем назвать того, кому достался этот кусочек, нережущим, а второго – режущим. Режущий делит остаток на три равные, по его мнению, части.

5) Игроки выбирают себе по кусочку из этих трех в следующем порядке: нережущий, Алиса, режущий. Ни у одного игрока нет причин завидовать тому, что получают остальные: если он завидует, значит, его тактика была ошибочной и выбирать ему следовало иначе. Доказательство см.: en.wikipedia.org/wiki/Selfridge-Conway_procedure.

16

S. J. Brams and A. D. Taylor. The Win-Win Solution: Guaranteeing Fair Shares to Everybody, Norton, New York (1999).

17

Z. Landau, O. Reid and I. Yershov. «A fair division solution to the problem of redistricting», Social Choice and Welfare 32 (2009) 479–492.

18

B. Alexeev and D. G. Mixon. «An impossibility Theorem for gerrymandering», American Mathematical Monthly 125 (2018) 878–884.

19

B. Gibson, M. Wilkinson and D. Kelly. «Let the pigeon drive the bus: pigeons can plan future routes in a room», Animal Cognition 15 (2012) 379–391.

20

Мой любимый пример – это политик, который поднял грандиозный шум по поводу напрасной траты денег на то, что он назвал «теорией лжи» (Lie theory). Слово lie он произносил «лай», то есть «ложь, неправда», и считал, что теория говорит именно об этом. На самом деле все не так. Софус Ли (Sophus Lie) был норвежским математиком, работа которого по непрерывным группам симметрий (группам Ли) и связанным с ними алгебрам имеет фундаментальное значение для обширных областей математики и еще большее – для физики. Политику указали на его заблуждение… но он продолжил выступать ровно так же, как прежде.

21

По техническим причинам мое замечание о пазлах не решает призовую задачу. Если бы решало, я был бы первым.

22

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).

23

G. Peano. «Sur une courbe qui remplit toute une aire plane», Mathematische Annalen 36 (1890) 157–160.

24

Здесь необходима тщательность, поскольку некоторые действительные числа не имеют единственного десятичного представления, например 0,500000… = 0,499999… Но с этим несложно разобраться.

25

E. Netto. «Beitrag zur Mannigfaltigkeitslehre», Journal für die Reine und Angewandte Mathematik 86 (1879) 263–268.

26

H. Sagan. «Some reflections on the emergence of space-filling curves: the way it could have happened and should have happened, but did not happen», Journal of the Franklin Institute 328 (1991) 419–430. Объяснение см. в: A. Jaffer. «Peano space-filling curves», http://people.csail.mit.edu/jaffer/Geometry/PSFC.

27

J. Lawder. «The application of space-filling curves to the storage and retrieval of multi-dimensional data», PhD Thesis, Birkbeck College, London (1999).

28

J. Bartholdi. «Some combinatorial applications of spacefilling curves», www2.isye.gatech.edu/~jjb/research/mow/mow.html.

29

H. Hahn. «Über die allgemeinste ebene Punktmenge, die stetiges Bild einer Strecke ist», Jahresbericht der Deutschen Mathematiker-Vereinigung, 23 (1914) 318–322. H. Hahn. «Mengentheoretische Charakterisierung der stetigen Kurven», Sitzungsberichte der Kaiserlichen Akademie der Wissenschaften, Wien 123 (1914) 2433–2489. S. Mazurkiewicz. «O aritmetzacji kontinuóv», Comptes Rendus de la Société Scientifique de Varsovie 6 (1913) 305–311 and 941–945.

30

Опубликовано в 1998 году: S. Arora, M. Sudan, R. Motwani, C. Lund and M. Szegedy. «Proof verification and the hardness of approximation problems», Journal of the Association for Computing Machinery 45 (1998) 501–555.

31

L. Babai. «Transparent proofs and limits to approximation», in: First European Congress of Mathematics. Progress in Mathematics 3 (eds. A. Joseph, F. Mignot, F. Murat, B. Prum and R. Rentschler) 31–91, Birkhäuser, Basel (1994).

32

C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow and R. Fergus. «Intriguing properties of neural networks», arXiv:1312.6199 (2013).

33

A. Shamir, I. Safran, E. Ronen and O. Dunkelman. «A simple explanation for the existence of adversarial examples with small Hamming distance», arXiv:1901.10861v1 [cs.LG] (2019).

34

Не следует путать граф с графиком функции, который представляет собой кривую, соотносящую переменную x со значением функции f(x). Например, парабола есть график функции f(x)= x².

35

Спасибо Робину Уилсону, который мягко указал мне на ошибку, когда я в одной из своих книг изложил все неправильно.

36

Если вы знаете, с какого участка начать, достаточно привести список только мостов в том порядке, в каком они используются. Последовательные мосты определяют общий участок суши, с которым оба соединены.

37

Это довольно легко доказать, пользуясь эйлеровой характеристикой разомкнутых маршрутов. Основная идея состоит в том, чтобы разбить гипотетический замкнутый маршрут, удалив один мост. Теперь у вас имеется разомкнутый маршрут, а удаленный мост соединял прежде его концы.

38

Оставшаяся часть этой главы основана на статье: D. Manlove. «Algorithms for kidney donation», London Mathematical Society Newsletter 475 (March 2018) 19–24.

39

Точная дата, когда Ферма сформулировал свою Великую теорему, наверняка неизвестна, но обычно считают, что это произошло в 1637 году.

40

То же можно сказать и о значительной части прикладной математики. Однако здесь есть разница: отношение самого математика. В чистой математике движущей силой является внутренняя логика предмета: не просто обезьянье любопытство, а поиск структуры и чувство того, где в наших представлениях имеются серьезные пробелы. В прикладной математике движущей силой служат в основном задачи, возникающие в «реальном мире», но сама она лучше переносит необоснованные сокращения и аппроксимации при поиске ответа, а ответ может иметь или не иметь практических следствий. Однако, как показывает эта глава, тема, которая в какой-то момент кажется совершенно бесполезной, может внезапно обрести громадное значение в практических вопросах в ходе серьезных изменений в культуре или технике. Более того, математика представляет собой внутренне взаимосвязанное целое, даже деление на чистую и прикладную искусственно. Теорема, которая кажется бесполезной сама по себе, может вдохновить или повлечь за собой результаты огромной практической важности.

41

Ответ:

p = 12277 385900 723407 383112 254544 721901 362713 421995 519,

q = 97117 113276 287886 345399 101127 363740 261423 928273 451.

Я нашел эти два простых числа методом проб и ошибок и перемножил их на компьютере, воспользовавшись символьной алгеброй. Это заняло несколько минут, причем время в основном тратилось на ручную замену случайных цифр, пока я не наткнулся-таки на простое число. После этого я велел компьютеру найти простые множители произведения. Расчет продолжался очень долго и не дал результата.

42

Если n есть степень простого числа p^k, то φ(n) = p^k – p^k-1. Для произведения простых степеней нужно перемножить эти выражения для всех простых степеней в разложении n на простые множители. Например, чтобы найти φ(675), запишем 675 = 3³5². Тогда φ(675) = (3³–3²)(5²–5) = (18)(20) = 360.

43

Более подробно о затронутых вопросах см.: Ian Stewart, Do Dice Play God?, Profile, London (2019), Chapters 15 and 16.

44

L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood and I. L. Chuang. «Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance», Nature 414 (2001) 883–887.

45

F. Arute and others. «Quantum supremacy using a programmable superconducting processor», Nature 574 (2019) 505–510.

46

J. Proos and C. Zalka. «Shor's discrete logarithm quantum algorithm for elliptic curves», Quantum Information and Computation 3 (2203).

47

M. Roetteler, M. Naehrig, K. Svore and K. Lauter. «Quantum resource estimates for computing elliptic curve discrete logarithms», in: ASIACRYPT 2017: Advances in Cryptology, Springer, New York (2017), 214–270.

48

Например, число –25 имеет квадратный корень 5i, потому что

(5i)² = 5i ∙ 5i = 5 ∙ 5 ∙ i ∙ i = 25i² = 25(–1) = –25.

Мало того, это число имеет и второй квадратный корень, – 5i, по аналогичным причинам.

49

Алгебраисты загоняют ситуацию в рамки, говоря, что квадратный корень из нуля равен нулю с кратностью два. То есть одно и то же значение возникает дважды в формальном, но вполне понятном смысле. Такое выражение, как x²–4, раскладывается на два множителя, x + 2 умножить на x – 2, которые дают, соответственно, два решения (x = –2 и x = +2) уравнения x²–4 = 0. Аналогично выражение x² раскладывается на два множителя x умножить на x. Просто так получается, что эти множители одинаковые.

50

Для действительного c функция z(t) = e^ct подчиняется дифференциальному уравнению dz/dt = cz при начальном условии z(0) = 1. Если мы определим экспоненциальную функцию для комплексного c так, что это уравнение тоже выполняется, что разумно, и положим c = i, то dz/dt = iz. Поскольку умножение на i поворачивает комплексные числа на 90 градусов, касательная к z(t) при изменении t располагается под прямым углом к вектору z(t), так что точка z(t) описывает окружность радиуса 1 с центром в начале координат. Она проходит по этой окружности с постоянной скоростью один радиан в единицу времени, поэтому в момент времени t ее положение определяется углом в t радиан. Из тригонометрии следует, что это точка cos t + i sin t.

51

Точнее говоря, там должно быть внутреннее произведение, которое определяет расстояния и углы.

52

Самым быстрым суперкомпьютером в 1988 году был Cray Y-MP, который стоил $20 млн (более $50 млн в сегодняшних ценах). Он с трудом потянул бы операционную систему Windows.

53

K. Shoemake. «Animating rotation with quaternion curves», Computer Graphics 19 (1985) 245–254.

54

L. Euler. «Découverte d'un nouveau principe de mécanique» (1752), Opera Omnia, Series Secunda 5, Orel Fusili Turici, Lausanne (1957), 81–108.

55

Свойство половинного угла важно в квантовой механике, где одно из определений квантового спина основано на кватернионах. Если волновая функция такой частицы, как фермион, поворачивается на 360°, ее спин меняется на обратный. (Это не то же самое, что поворот самой частицы.) Чтобы вернуть спин к начальному значению, волновая функция должна повернуться на 720°. Единичные кватернионы образуют «двойное покрытие» вращений.

56

C. Brandt, C. von Tycowicz and K. Hildebrandt. «Geometric flows of curves in shape space for processing motion of deformable objects», Computer Graphics Forum 35 (2016) 295–305.

57

. www.syfy.com/syfywire/it-took-more-cgi-than-you-think-to-bring-carrie-fisher-into-the-rise-of-skywalker.

58

T. Takagi and M. Sugeno. «Fuzzy identification of systems and its application to modeling and control», IEEE Transactions on Systems, Man and Cybernetics 15 (1985) 116–132.

59

Это JFIF-кодирование, используемое в Сети. EXIF-кодирование для камер включает в файл также «метаданные» с описанием параметров камеры, таких как дата, время и экспозиция.

60

A. Jain and S. Pankanti. «Automated fingerprint identification and imaging systems», in: Advances in Fingerprint Technology (eds. C. Lee and R. E. Gaensslen), CRC Press, (2001) 275–326.

61

N. Ashby. «Relativity in the Global Positioning System», Living Reviews in Relativity 6 (2003) 1; doi: 10.12942/lrr-2003–1.

62

Более точно, Z = Σ exp(–βH), где сумма берется по всем конфигурациям спиновых переменных.

63

Если β = 1/k_BT, где k_B – постоянная Больцмана, то формула принимает вид:

64

Формула выглядит так:

где H – напряженность внешнего поля, а J – сила взаимодействия между спинами. При отсутствии внешнего поля H = 0, следовательно, sinh(βH) = 0, и вся дробь равна нулю.

65

Y.-P. Ma, I. Sudakov, C. Strong, and K. M. Golden. «Ising model for melt ponds on Arctic sea ice», New Journal of Physics 21 (2019) 063029.

66

S. Tanaka. «Topological analysis of point singularities in stimulus preference maps of the primary visual cortex», Proceedings of the Royal Society of London B 261 (1995) 81–88.

67

«Lobster telescope has an eye for X-rays», http://www.sciencedaily.com/releases/2006/04/060404194138.htm.

68

На формальном языке кривая есть образ границы диска при преобразовании диска в сферу. Кривая может пересекать саму себя, а диск может сминаться.

69

J. J. Berwald, M. Gidea and M. Vejdemo-Johansson. «Automatic recognition and tagging of topologically different regimes in dynamical systems», Discontinuity, Nonlinearity, and Complexity 3 (2014) 413–426.

70

F. A. Khasawneh and E. Munch. «Chatter detection in turning using persistent homology», Mechanical Systems and Signal Procassing 70 (2016) 527–541.

71

C. J. Tralie and J. A. Perea. «(Quasi) periodicity quantification in video data, using topology», SIAM Journal on Imaging Science 11 (2018) 1049–1077.

72

S. Emrani, T. Gentimis, and H. Krim. «Persistent homology of delay embeddings and its application to wheeze detection», IEEE Signal Processing Letters 21 (2014) 459–463.