https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Fedja&feedformat=atom AoPS Wiki - User contributions [en] 2020-12-05T00:11:45Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Fractal&diff=44179 Fractal 2012-01-08T22:28:55Z <p>Fedja: </p> <hr /> <div>A fractal is defined as a figure that does not become simpler under any level of magnification.<br /> <br /> ==Mandelbrot set==<br /> Probably the most well-known example of a fractal, the Mandelbrot set is the set of all points &lt;math&gt;c&lt;/math&gt; in the [[complex plane]] for which the [[sequence]] &lt;math&gt;z_0=0, z_{n+1}=z_n^2+c&lt;/math&gt; is bounded.<br /> <br /> This fractal is NOT [[self-similarity|self-similar]]. However, it is almost self-similar. If one were to plot all points in the Mandelbrot set using the complex plane, it would look like this.<br /> <br /> &lt;asy&gt;<br /> size(400);<br /> <br /> int f(pair c)<br /> {<br /> pair z=(0,0);<br /> int k;<br /> for(k=0;(k&lt;99)&amp;&amp;(abs(z)&lt;10);++k) z=z^2+c;<br /> return floor(k/10);<br /> }<br /> <br /> pen[] p={white,yellow,orange,blue,green,orange,magenta,red,brown,black};<br /> <br /> real h=0.007; <br /> <br /> for(int k=-350;k&lt;70;++k)<br /> for(int m=0;m&lt;200;++m)<br /> {<br /> pair P=h*((k,0)+m*dir(60));<br /> int n=f(P);<br /> if (n&gt;0)<br /> {<br /> dot(P,linewidth(1.5)+p[n]); if(m&gt;0) dot((P.x,-P.y),linewidth(1.5)+p[n]);<br /> }<br /> }<br /> &lt;/asy&gt;</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Base_numbers&diff=43856 Talk:Base numbers 2011-12-23T18:34:40Z <p>Fedja: </p> <hr /> <div>This is a great start to an article. The early part could use a little white space. Students who really need to learn about base numbers from this article are going to need a mental pause, and multiple examples. A section on conversions would be nice.--[[User:MCrawford|MCrawford]] 00:42, 20 June 2006 (EDT)<br /> <br /> Hmmm... What do you mean by '''base doesn't need to be an integer'''? Especially suspicious is the idea to use '''complex''' bases. What numbers are you going to represent in such bases and what are the digits? In my opinion, this part (at least, as written) is rather confusing than revealing... --[[User:Fedja|Fedja]] 19:34, 22 June 2006 (EDT)<br /> <br /> We can have base &lt;math&gt;i&lt;/math&gt;, base &lt;math&gt;\phi&lt;/math&gt;, and improper fractional bases like 3/2. In a rational base, any integer may be represented without a decimal point in that base. For complex and irrational bases, we use (I think) 0 or 1 as digits. For a fractional base p/q with max(p,q)=a, we use 0 up to a-1 for digits, i.e. for 3/2, 0,1,2 are digits; for 1/4, we use 0,1,2,3. --[[User:Solafidefarms|solafidefarms]] 21:11, 22 June 2006 (EDT)<br /> <br /> Hmmm..., so how would you represent, say 4 using base 3/2 and digits 0,1, and 2? Also, what would, say, 4 be when written in base &lt;math&gt;i&lt;/math&gt; (the latter question is especially interesting, because all possible powers of &lt;math&gt;i&lt;/math&gt; are &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;i&lt;/math&gt;, &lt;math&gt;-1&lt;/math&gt;, and &lt;math&gt;-i&lt;/math&gt;). Maybe you mean something here but, since even I cannot understand you, there is no hope that 12 year old kids will...--[[User:Fedja|Fedja]] 21:42, 22 June 2006 (EDT)<br /> <br /> First, non-integral bases are not an introductory topic; more of Intermediate or Olympiad. (I have heard it said by several that my work in improper fractional bases is above even that level.) <br /> <br /> There is a special method of conversion which works on any rational base greater than 1, not just integral bases, which we use instead of power methods for improper fractional bases. Basically, we let the number we wish to convert be the rightmost digit. Then, while any of the &quot;digits&quot; of our number are greater than/equal to the numerator of our base, we subtract the numerator from that digit and add the denominator to the next digit to the left. I.e., to convert the number 23 to base 7 using this method, we start with the digit 23. 23&gt;7, so we subtract 7 and add 1 to the next digit: 1|16. (We use | as a matter of convenience, to separate the digits.) Again we do it, till we get 3|2. Now none of the digits are more than 7, so we are through, and 23_7=32_10.<br /> <br /> For, say, 7, in base 3/2, we start with 7. Subtract 2 3s and add 2 2s: 4|1. Again, and we have 211_3/2=7_10. If you want to read more, I have a paper on improper fractional bases at [http://billydorminy.homelinux.com/sciencefair/researchpaper4.pdf]. (I went to the [[International Science and Engineering Fair]] with improper fractional bases :) ) <br /> <br /> I'm not sure about complex bases. Complex bases are not terribly well-explored. A google doesn't turn up much.<br /> <br /> Now then, I am strongly in favor of putting links to individual pages on complex/irrational/fractional bases, because I could go on forever on improper fractional bases.--[[User:Solafidefarms|solafidefarms]] 22:08, 22 June 2006 (EDT)<br /> <br /> OK, I looked at your paper and, at least, understand now what you mean by &quot;fractional bases&quot; (though complex and irrational ones remain a mystery to me). I think you should ask some of the admins whether it is an appropriate stuff for AoPSWiki, and, if they decide it is, write a separate article on it first. If you succeed, there will always be time to link it to this one.--[[User:Fedja|Fedja]] 23:01, 22 June 2006 (EDT)<br /> <br /> Indeed, yes, complex bases I know little about. Irrational bases I've been exposed to in Art and Craft of Computer Programming a little, but they are really strange. I'll work sometime on an improper fractional base article sometime separately. --[[User:Solafidefarms|solafidefarms]] 23:09, 22 June 2006 (EDT)<br /> <br /> <br /> All math topics are fine to write about. Just create new article appropriately when the amount of content justifies its own article.--[[User:MCrawford|MCrawford]] 23:28, 22 June 2006 (EDT)<br /> <br /> Complex number bases do exist as proven by this AIME problem: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=436603#p436603 But that's about all I know about complex numbers for number bases :( [[User:Joml88|Joe]] 10:07, 23 June 2006 (EDT)<br /> <br /> Neither of the really important properties of bases are mentioned in this article -- nowhere does it say that base representations exist nor that they are unique. Nor, in fact, does it address at all the notion of representing any numbers other than smallish integers. --[[User:JBL|JBL]] 09:00, 17 July 2006 (EDT)<br /> <br /> ----<br /> <br /> Ack, don't ya'll think we should have just a /little/ more text on here? On Wikipedia, generally even if there is a sub-article an overview remains on the main page (see [http://en.wikipedia.org/wiki/History_of_the_United_States_%281865%E2%80%931918%29])<br /> for an example). Besides which, improper fractional bases needs a link :D. --[[User:Solafidefarms|solafidefarms]] 22:13, 7 August 2006 (EDT)<br /> <br /> Do you mean you want a link to [[Improper fractional base]] in the See Also section? If so, I'll add it. Remove it if it doesn't belong here. <br /> --[[User:Xantos C. Guin|Xantos C. Guin]] 23:25, 7 August 2006 (EDT)<br /> <br /> After closer examination of this article, I decided that the link to [[Improper fractional base]] belongs in the Base Number Topics section.<br /> --[[User:Xantos C. Guin|Xantos C. Guin]] 23:28, 7 August 2006 (EDT)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Base_numbers&diff=43855 Talk:Base numbers 2011-12-23T18:33:07Z <p>Fedja: </p> <hr /> <div>This is a great start to an article. The early part could use a little white space. Students who really need to learn about base numbers from this article are going to need a mental pause, and multiple examples. A section on conversions would be nice.--[[User:MCrawford|MCrawford]] 00:42, 20 June 2006 (EDT)<br /> <br /> Hmmm... What do you mean by '''base doesn't need to be an integer'''? Especially suspicious is the idea to use '''complex''' bases. What numbers are you going to represent in such bases and what are the digits? In my opinion, this part (at least, as written) is rather confusing than revealing... --[[User:Fedja|Fedja]] 19:34, 22 June 2006 (EDT)<br /> <br /> We can have base &lt;math&gt;i&lt;/math&gt;, base &lt;math&gt;\phi&lt;/math&gt;, and improper fractional bases like 3/2. In a rational base, any integer may be represented without a decimal point in that base. For complex and irrational bases, we use (I think) 0 or 1 as digits. For a fractional base p/q with max(p,q)=a, we use 0 up to a-1 for digits, i.e. for 3/2, 0,1,2 are digits; for 1/4, we use 0,1,2,3. --[[User:Solafidefarms|solafidefarms]] 21:11, 22 June 2006 (EDT)&lt;math&gt;<br /> <br /> Hmmm..., so how would you represent, say 4 using base 3/2 and digits 0,1, and 2? Also, what would, say, 4 be when written in base &lt;/math&gt;i&lt;math&gt; (the latter question is especially interesting, because all possible powers of &lt;/math&gt;i&lt;math&gt; are &lt;/math&gt;1&lt;math&gt;, &lt;/math&gt;i&lt;math&gt;, &lt;/math&gt;-1&lt;math&gt;, and &lt;/math&gt;-i). Maybe you mean something here but, since even I cannot understand you, there is no hope that 12 year old kids will...--[[User:Fedja|Fedja]] 21:42, 22 June 2006 (EDT)<br /> <br /> First, non-integral bases are not an introductory topic; more of Intermediate or Olympiad. (I have heard it said by several that my work in improper fractional bases is above even that level.) <br /> <br /> There is a special method of conversion which works on any rational base greater than 1, not just integral bases, which we use instead of power methods for improper fractional bases. Basically, we let the number we wish to convert be the rightmost digit. Then, while any of the &quot;digits&quot; of our number are greater than/equal to the numerator of our base, we subtract the numerator from that digit and add the denominator to the next digit to the left. I.e., to convert the number 23 to base 7 using this method, we start with the digit 23. 23&gt;7, so we subtract 7 and add 1 to the next digit: 1|16. (We use | as a matter of convenience, to separate the digits.) Again we do it, till we get 3|2. Now none of the digits are more than 7, so we are through, and 23_7=32_10.<br /> <br /> For, say, 7, in base 3/2, we start with 7. Subtract 2 3s and add 2 2s: 4|1. Again, and we have 211_3/2=7_10. If you want to read more, I have a paper on improper fractional bases at [http://billydorminy.homelinux.com/sciencefair/researchpaper4.pdf]. (I went to the [[International Science and Engineering Fair]] with improper fractional bases :) ) <br /> <br /> I'm not sure about complex bases. Complex bases are not terribly well-explored. A google doesn't turn up much.<br /> <br /> Now then, I am strongly in favor of putting links to individual pages on complex/irrational/fractional bases, because I could go on forever on improper fractional bases.--[[User:Solafidefarms|solafidefarms]] 22:08, 22 June 2006 (EDT)<br /> <br /> OK, I looked at your paper and, at least, understand now what you mean by &quot;fractional bases&quot; (though complex and irrational ones remain a mystery to me). I think you should ask some of the admins whether it is an appropriate stuff for AoPSWiki, and, if they decide it is, write a separate article on it first. If you succeed, there will always be time to link it to this one.--[[User:Fedja|Fedja]] 23:01, 22 June 2006 (EDT)<br /> <br /> Indeed, yes, complex bases I know little about. Irrational bases I've been exposed to in Art and Craft of Computer Programming a little, but they are really strange. I'll work sometime on an improper fractional base article sometime separately. --[[User:Solafidefarms|solafidefarms]] 23:09, 22 June 2006 (EDT)<br /> <br /> <br /> All math topics are fine to write about. Just create new article appropriately when the amount of content justifies its own article.--[[User:MCrawford|MCrawford]] 23:28, 22 June 2006 (EDT)<br /> <br /> Complex number bases do exist as proven by this AIME problem: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=436603#p436603 But that's about all I know about complex numbers for number bases :( [[User:Joml88|Joe]] 10:07, 23 June 2006 (EDT)<br /> <br /> Neither of the really important properties of bases are mentioned in this article -- nowhere does it say that base representations exist nor that they are unique. Nor, in fact, does it address at all the notion of representing any numbers other than smallish integers. --[[User:JBL|JBL]] 09:00, 17 July 2006 (EDT)<br /> <br /> ----<br /> <br /> Ack, don't ya'll think we should have just a /little/ more text on here? On Wikipedia, generally even if there is a sub-article an overview remains on the main page (see [http://en.wikipedia.org/wiki/History_of_the_United_States_%281865%E2%80%931918%29])<br /> for an example). Besides which, improper fractional bases needs a link :D. --[[User:Solafidefarms|solafidefarms]] 22:13, 7 August 2006 (EDT)<br /> <br /> Do you mean you want a link to [[Improper fractional base]] in the See Also section? If so, I'll add it. Remove it if it doesn't belong here. <br /> --[[User:Xantos C. Guin|Xantos C. Guin]] 23:25, 7 August 2006 (EDT)<br /> <br /> After closer examination of this article, I decided that the link to [[Improper fractional base]] belongs in the Base Number Topics section.<br /> --[[User:Xantos C. Guin|Xantos C. Guin]] 23:28, 7 August 2006 (EDT)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Advanced_Configuration&diff=39693 Asymptote: Advanced Configuration 2011-06-18T01:43:41Z <p>Fedja: corrected the arguments line to agree with the new conventions</p> <hr /> <div>{{Asymptote}}<br /> <br /> There are two things that Asymptote users commonly would like to do with their figures: make the images output in a different format, and include Asymptote code directly into LaTeX files. <br /> ==PDF format and beyond==<br /> Asymptote can easily make your images in pdf format rather than eps format, with the help of a program called '''GhostScript'''.<br /> ===GhostScript===<br /> To download and install GhostScript on Windows:<br /> # Go to [http://sourceforge.net/projects/ghostscript/ sourceforge.net/projects/ghostscript] and click Download GhostScript. This should bring you to a box containing several formats of the latest release. Click on the link to download AFPL or GPL Ghostscript, and the next page should have an option to download an file ending in &lt;tt&gt;.exe&lt;/tt&gt; (for version 8.54, the file is &lt;tt&gt;gs854w32.exe&lt;/tt&gt;). <br /> # Click on the link for the .exe file, and a download window will pop up in your browser. Choose to save the file, and take note of where on your hard drive you saved it to. Let's say you saved it to the folder &lt;tt&gt;D:\downloads\Ghostscript&lt;/tt&gt;.<br /> # When the download is complete, browse to &lt;tt&gt;D:\downloads\Ghostscript&lt;/tt&gt; in your files and double-click on the .exe file (&lt;tt&gt;gs854w32.exe&lt;/tt&gt;). This will bring you to an installation window. Click Setup.<br /> # After the installer extracts the required files, you will see a new window with the option to change the installation folder (the default will be &lt;tt&gt;C:\Program Files\gs&lt;/tt&gt;) and an option to select the folder in the start menu to which a shortcut will be added. When you have finished, click Install.<br /> <br /> ===PDF output configuration===<br /> Although gsview can configured as the pdf viewer, we recommend using the default pdf viewer, Acrobat Reader.<br /> <br /> Now open TeXnicCenter. Go to the Tools menu and click Customize, then go to the Tools tab. Click to modify your Asymptote tool that you made in the Interactive Mode section. In the Arguments line, put<br /> -batchView -tex &quot;pdflatex&quot; %tc-*.asy<br /> Now if you open the file test.asy in TeXnicCenter again, which contains the code<br /> draw((0,0)--(100,100));<br /> draw((0,100)--(100,0));<br /> dot((50,50));<br /> label(&quot;P&quot;,(50,50),S);<br /> and press Alt+A (or your corresponding hotkey), voila! You have made a pdf document with your image.<br /> <br /> In order to make Asymptote output files in .jpg or other formats, you must use a program such as ImageMagick that is capable of converting .eps files to many other image formats. If you have ImageMagick installed (you can obtain it [[http://www.imagemagick.org/script/binary-releases.php here]] and install it from the download), you can simply type at an MSDOS command prompt:<br /> convert test.eps test.jpg<br /> and the file test.jpg will be produced. See [[http://www.imagemagick.org/script/index.php the ImageMagick home page]] for more information on converting images between file formats.<br /> <br /> ==Using Asymptote in LaTeX==<br /> One of Asymptote's main advantages as a graphics language is its incredible compatibility with LaTeX. Once you have it configured correctly, you can simply type a &lt;tt&gt;\begin{asy} ... \end{asy}&lt;/tt&gt; block in a figure environment in your LaTeX file, and an image will be produced in your document! <br /> <br /> First you need to get LaTeX to see Asymptote. In order to do this, you must add the package &lt;tt&gt;asymptote.sty&lt;/tt&gt; to your LaTeX package directory (this file can be found in your Asymptote directory, by default &lt;tt&gt;C:\Program Files\Asymptote&lt;/tt&gt;). For example, if you are using MikTeX (recommended) and MikTeX is installed to &lt;tt&gt;C:\Program Files&lt;/tt&gt; on your computer, you can use the following steps to get MikTeX to see Asymptote:<br /> # Browse to the folder &lt;tt&gt;C:\Program Files\MiKTeX 2.x\tex\latex\&lt;/tt&gt; (&lt;small&gt;''replace 2.x by the version on your machine''&lt;/small&gt;).<br /> # Here, create a new folder and call it &lt;tt&gt;asymptote&lt;/tt&gt;. <br /> # Open your new folder. For full functionality, copy the files &lt;tt&gt;asymptote.sty&lt;/tt&gt; and &lt;tt&gt;asycolors.sty&lt;/tt&gt; from &lt;tt&gt;C:\Program Files\Asymptote&lt;/tt&gt; into this new asymptote folder.<br /> # Open MikTeX Options. This is most likely a shortcut in your Start Menu along with MikTeX; if it is not here, go to &lt;tt&gt;C:\Program Files\MiKTeX 2.x\miktex\bin&lt;/tt&gt; and click on &lt;tt&gt;mo.exe&lt;/tt&gt; (&lt;small&gt;''replace 2.x by the version of MikTeX on your machine''&lt;/small&gt;). If using MikTeX 2.7 or 2.8 on Vista or Windows 7 then in the Start Menu go to MikTeX 2.x, Maintenance(Admin), Settings(Admin)<br /> # In the General tab, you will see a section labeled File Name Database with a button that says Refresh Now. Click it to refresh your file name database. MikTeX should now see your Asymptote style files.<br /> <br /> Now, you should be ready to include your figures in your LaTeX document. Create a test file called example.tex, and copy-and-paste the following code into the document:<br /> <br /> \documentclass{article}<br /> \usepackage[pdftex]{graphicx}<br /> \usepackage{asymptote}<br /> \begin{document}<br /> Hello. <br /> I like to make pics with Asymptote like this one:<br /> \begin{figure}[h]<br /> \begin{asy}<br /> include graph;<br /> size(1inch);<br /> filldraw(circle((0,0),1),yellow,black);<br /> fill(circle((-.3,.4),.1),black);<br /> fill(circle((.3,.4),.1),black);<br /> draw(arc((0,0),.5,-140,-40));<br /> \end{asy}<br /> \end{figure}<br /> \par It makes me happy, <br /> since I can still type my normal LaTeX stuff around it: <br /> $$\int_0^{\pi}{\sin{x}}\,dx=2$$<br /> \end{document}<br /> <br /> Notice that the &lt;tt&gt;\end{asy}&lt;/tt&gt; line is justified '''all the way to the left, on a line by itself'''. This is VERY IMPORTANT for the asymptote.sty package to find the end of the Asymptote code; there can be no whitespaces or other characters on the line containing &lt;tt&gt;\end{asy}&lt;/tt&gt;. <br /> <br /> You are not quite done yet - LaTeX will not output the image the first time it compiles the document. To compile this file, you must:<br /> # Pass it once through LaTeX without viewing the output (click Build in TeXnicCenter; this extracts your asy code into a .asy file.)<br /> # Run Asymptote on the new file example.asy (pressing Alt+A as normal in TeXnicCenter will work, since it only looks at the title example.)<br /> # Finally, run it again through LaTeX (click Build and View Current File in TeXnicCenter). Your output should look like:<br /> <br /> ----<br /> <br /> Hello. I like to make pics with Asymptote like this one:<br /> <br /> [[Image:Smiley.jpg]]<br /> <br /> It makes me happy, since I can still type my normal LaTeX stuff around it:<br /> <br /> &lt;math&gt;{\int_0^{\pi}{\sin{x}}\,{dx}=2}&lt;/math&gt;<br /> <br /> ----<br /> <br /> If you do not want to have to go through all 3 steps above every time you want to compile your LaTeX document, you have several options: (1) You can create your Asymptote files separately in eps format, and include them into your LaTeX document with the &lt;tt&gt;\includegraphics&lt;/tt&gt; command. (2) You can create a DOS batch file to run the three commands in order, and call this batch file using a TeXnicCenter tool on your current file. The advantage of the former is that your LaTeX document will take less time to compile since the images are already made, and the advantage of the latter is the clean, readable format of the &lt;tt&gt;\begin{asy} ... \end{asy}&lt;/tt&gt; blocks in your code. This guide does not provide detail on implementing such methods. See [[http://www.computerhope.com/batch.htm#11 here]] for a good reference on DOS batch files and Windows batch commands.<br /> <br /> ==Showing Asymptote error messages in TeXnicCenter==<br /> There are two methods:<br /> <br /> (1) When running Asymptote from inside TexnicCenter, the DOS window closes too quickly to see any error messages. These messages may be crucial to correcting the code. TeXnicCenter can be persuaded to show the messages with a new tool, or, if you wish, overwriting the original Asymptote tool.<br /> <br /> The following instructions assume that Asymptote and TeXnicCenter have been saved in the default directories C:\Program Files\Asymptote and C:\Program Files\TeXnicCenter; change them as necessary.<br /> * In Notepad (or TeXnicCenter) create a new file called asymptote.bat and save it in C:\Program Files\Asymptote. Copy and paste the following into the file:<br /> &lt;div style=&quot;overflow:auto; width:40em;&quot;&gt;&lt;small&gt;&lt;pre&gt;<br /> echo off <br /> echo Asymptote is working ... please wait <br /> &quot;C:\Program Files\Asymptote\redir.exe&quot; -e %1 &quot;C:\progra~1\Asymptote\asy.exe&quot; -batchView -tex &quot;pdflatex&quot; -align C -f &quot;pdf&quot; %2 <br /> find /i &quot;.asy&quot; %3 &gt;nul <br /> If errorlevel 1 goto end <br /> &quot;C:\Program Files\TeXnicCenter\TEXCNTR.EXE&quot; /ddecmd &quot;[open('%3')]&quot; <br /> :end<br /> &lt;/pre&gt;&lt;/small&gt;&lt;/div&gt;<br /> * Download [[http://www.artofproblemsolving.com/files/redir.zip redir.zip]], extract redir.exe, virus check it and save in C:\Program Files\Asymptote<br /> * In TexnicCenter, Tools-&gt;Customise...-&gt;Tools put in either a new tool or change the current Asymptote tool: <br /> ** Commands: &quot;C:\Program Files\Asymptote\asymptote.bat&quot; <br /> ** Arguments: %tc_asy.log %tc &quot;%dc\%tc_asy.log&quot; <br /> ** Initial directory: %dc <br /> : then press Close<br /> <br /> Now when you run Asymptote on &lt;tt&gt;file.tex&lt;/tt&gt; from inside TexnicCenter the error messages, if any, will be saved in &lt;tt&gt;file_asy.log&lt;/tt&gt;. If there are any error messages then this file will open in TeXnicCenter showing you the messages. When you have eliminated all the errors nothing will show in TeXnicCenter.<br /> <br /> (2) This method has more steps to implement, but is worth it. It is only applicable when you have Asymptote code inside the Asymptote Environment in LaTeX code. Simply implement the following steps to have it so that you can compile Asymptote images along with the LaTeX just by clicking 'Build.' It also displays error messages right on the TeXnicCenter output box. (It will appear at the very end.)<br /> <br /> *Go to Tools &gt; Define Output Profiles... (or press Alt+F7).<br /> *Select your current output profile (most likely it will be LaTeX =&gt; PDF).<br /> *Click on 'Copy' at the bottom.<br /> *Make the profile's name 'LaTeX =&gt; PDF(Asymptote)' (without the single quotes).<br /> *Click on the 'Postprocessor' tab.<br /> *Click on the button that looks like a dotted square (when you hover your mouse over it, the description should be 'New (Insert)').<br /> <br /> *Type in 'Asymptote'.<br /> **Executable: C:\Program Files\Asymptote\asy.exe<br /> **Arguments: -batchView -tex &quot;pdflatex&quot; %tm<br /> <br /> *Click on the New button again.<br /> *Type in 'LaTeXComp'.<br /> **Executable: C:\Program Files\MiKTeX 2.7\miktex\bin\pdflatex.exe<br /> **Arguments: -interaction=nonstopmode &quot;%pm&quot;<br /> <br /> *Click on the New button again.<br /> *Type in 'BibTex'.<br /> **Executable: C:\Program Files\MiKTeX 2.7\miktex\bin\bibtex.exe<br /> **Arguments: &quot;%bm&quot;<br /> <br /> *Click on the New button again.<br /> *Type in 'MakeIndex'.<br /> **Executable: C:\Program Files\MiKTeX 2.7\miktex\bin\makeindex.exe<br /> **Arguments: &quot;%bm&quot;<br /> <br /> *Click 'Ok' at the bottom.<br /> *Go to Tools &gt; Select Output Profile...<br /> *Select the profile you just created.<br /> <br /> Now you're done. All you have to do is click on 'Build' to compile both your LaTeX and embedded Asymptote code. What I would suggest is to only use this profile whenever you start a new asymptote environment or you updated a previously existing environment. This way, the building process will occur faster. (When you use this profile, your LaTeX document is compiled, then your Asymptote code is compiled, then your LaTeX document is compiled once more. So this will caus build time to be increased by around 5-10 seconds.)<br /> <br /> Note that if you have any errors in the Asymptote code, they will appear at the very bottom in the output box in TeXnicCenter.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=File:Seva.jpg&diff=38682 File:Seva.jpg 2011-05-24T16:11:15Z <p>Fedja: uploaded a new version of &quot;File:Seva.jpg&quot;:&amp;#32;made it smaller</p> <hr /> <div>The file for later use in an article</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=File:Seva.jpg&diff=38681 File:Seva.jpg 2011-05-24T15:57:41Z <p>Fedja: The file for later use in an article</p> <hr /> <div>The file for later use in an article</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_12A_Problems/Problem_22&diff=36450 2008 AMC 12A Problems/Problem 22 2011-01-25T05:35:04Z <p>Fedja: /* Solution 1 (trigonometry) */</p> <hr /> <div>{{duplicate|[[2008 AMC 12A Problems|2008 AMC 12A #22]] and [[2008 AMC 10A Problems/Problem 25|2004 AMC 10A #25]]}}<br /> ==Problem==<br /> A round table has radius &lt;math&gt;4&lt;/math&gt;. Six rectangular place mats are placed on the table. Each place mat has width &lt;math&gt;1&lt;/math&gt; and length &lt;math&gt;x&lt;/math&gt; as shown. They are positioned so that each mat has two corners on the edge of the table, these two corners being end points of the same side of length &lt;math&gt;x&lt;/math&gt;. Further, the mats are positioned so that the inner corners each touch an inner corner of an adjacent mat. What is &lt;math&gt;x&lt;/math&gt;?<br /> <br /> &lt;asy&gt;unitsize(4mm);<br /> defaultpen(linewidth(.8)+fontsize(8));<br /> draw(Circle((0,0),4));<br /> path mat=(-2.687,-1.5513)--(-2.687,1.5513)--(-3.687,1.5513)--(-3.687,-1.5513)--cycle;<br /> draw(mat);<br /> draw(rotate(60)*mat);<br /> draw(rotate(120)*mat);<br /> draw(rotate(180)*mat);<br /> draw(rotate(240)*mat);<br /> draw(rotate(300)*mat);<br /> label(&quot;$$x$$&quot;,(-1.55,2.1),E);<br /> label(&quot;$$1$$&quot;,(-0.5,3.8),S);&lt;/asy&gt;<br /> <br /> &lt;math&gt;\mathrm{(A)}\ 2\sqrt{5}-\sqrt{3}\qquad\mathrm{(B)}\ 3\qquad\mathrm{(C)}\ \frac{3\sqrt{7}-\sqrt{3}}{2}\qquad\mathrm{(D)}\ 2\sqrt{3}\qquad\mathrm{(E)}\ \frac{5+2\sqrt{3}}{2}&lt;/math&gt;<br /> <br /> ==Solution==<br /> === Solution 1 (trigonometry) ===<br /> Let one of the mats be &lt;math&gt;ABCD&lt;/math&gt;, and the center be &lt;math&gt;O&lt;/math&gt; as shown: <br /> <br /> &lt;asy&gt;unitsize(8mm);<br /> defaultpen(linewidth(.8)+fontsize(8));<br /> draw(Circle((0,0),4));<br /> path mat=(-2.687,-1.5513)--(-2.687,1.5513)--(-3.687,1.5513)--(-3.687,-1.5513)--cycle;<br /> draw(mat);<br /> draw(rotate(60)*mat);<br /> draw(rotate(120)*mat);<br /> draw(rotate(180)*mat);<br /> draw(rotate(240)*mat);<br /> draw(rotate(300)*mat);<br /> label(&quot;$$x$$&quot;,(-1.55,2.1),E);<br /> label(&quot;$$x$$&quot;,(0.03,1.5),E);<br /> label(&quot;$$A$$&quot;,(-3.6,2.5513),E);<br /> label(&quot;$$B$$&quot;,(-3.15,1.35),E);<br /> label(&quot;$$C$$&quot;,(0.05,3.20),E);<br /> label(&quot;$$D$$&quot;,(-0.75,4.15),E);<br /> label(&quot;$$O$$&quot;,(0.00,-0.10),E);<br /> label(&quot;$$1$$&quot;,(-0.1,3.8),S);<br /> label(&quot;$$4$$&quot;,(-0.4,2.2),S);<br /> draw((0,0)--(0,3.103));<br /> draw((0,0)--(-2.687,1.5513));<br /> draw((0,0)--(-0.5,3.9686));&lt;/asy&gt;<br /> <br /> Since there are &lt;math&gt;6&lt;/math&gt; mats, &lt;math&gt;\Delta BOC&lt;/math&gt; is [[equilateral]]. So, &lt;math&gt;BC=CO=x&lt;/math&gt;. Also, &lt;math&gt;\angle OCD = \angle OCB + \angle BCD = 60^\circ+90^\circ=150^\circ&lt;/math&gt;. <br /> <br /> By the [[Law of Cosines]]: &lt;math&gt;4^2=1^2+x^2-2\cdot1\cdot x \cdot \cos(150^\circ) \Rightarrow x^2 + x\sqrt{3} - 15 = 0 \Rightarrow x = \frac{-\sqrt{3}\pm 3\sqrt{7}}{2}&lt;/math&gt;. <br /> <br /> Since &lt;math&gt;x&lt;/math&gt; must be positive, &lt;math&gt;x = \frac{3\sqrt{7}-\sqrt{3}}{2} \Rightarrow C&lt;/math&gt;.<br /> <br /> === Solution 2 (without trigonometry) ===<br /> <br /> [http://www.artofproblemsolving.com/Community/AoPS_Y_MJ_Transcripts.php?mj_id=218 See Math Jam]<br /> <br /> ==See Also==<br /> {{AMC12 box|year=2008|ab=A|num-b=21|num-a=23}}<br /> {{AMC10 box|year=2008|ab=A|num-b=24|after=Last Question}}<br /> <br /> [[Category:Introductory Geometry Problems]]<br /> [[Category:Introductory Trigonometry Problems]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_10A_Problems/Problem_21&diff=36449 2008 AMC 10A Problems/Problem 21 2011-01-25T05:33:29Z <p>Fedja: /* Solution */</p> <hr /> <div>==Problem==<br /> A [[cube]] with side length &lt;math&gt;1&lt;/math&gt; is sliced by a plane that passes through two diagonally opposite vertices &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;C&lt;/math&gt; and the [[midpoint]]s &lt;math&gt;B&lt;/math&gt; and &lt;math&gt;D&lt;/math&gt; of two opposite edges not containing &lt;math&gt;A&lt;/math&gt; or &lt;math&gt;C&lt;/math&gt;, as shown. What is the area of [[quadrilateral]] &lt;math&gt;ABCD&lt;/math&gt;?<br /> <br /> &lt;asy&gt;<br /> import three;<br /> unitsize(3cm);<br /> defaultpen(fontsize(8)+linewidth(0.7));<br /> currentprojection=obliqueX;<br /> <br /> draw((0.5,0,0)--(0,0,0)--(0,0,1)--(0,0,0)--(0,1,0),linetype(&quot;4 4&quot;));<br /> draw((0.5,0,1)--(0,0,1)--(0,1,1)--(0.5,1,1)--(0.5,0,1)--(0.5,0,0)--(0.5,1,0)--(0.5,1,1));<br /> draw((0.5,1,0)--(0,1,0)--(0,1,1));<br /> dot((0.5,0,0));<br /> label(&quot;A$&quot;,(0.5,0,0),WSW);<br /> dot((0,1,1));<br /> label(&quot;$C$&quot;,(0,1,1),NE);<br /> dot((0.5,1,0.5));<br /> label(&quot;$D$&quot;,(0.5,1,0.5),ESE);<br /> dot((0,0,0.5));<br /> label(&quot;$B$&quot;,(0,0,0.5),NW);&lt;/asy&gt;<br /> <br /> &lt;math&gt;\mathrm{(A)}\ \frac{\sqrt{6}}{2}\qquad\mathrm{(B)}\ \frac{5}{4}\qquad\mathrm{(C)}\ \sqrt{2}\qquad\mathrm{(D)}\ \frac{5}{8}\qquad\mathrm{(E)}\ \frac{3}{4}&lt;/math&gt;<br /> <br /> ==Solution==<br /> &lt;center&gt;&lt;asy&gt;<br /> import three;<br /> unitsize(3cm);<br /> defaultpen(fontsize(8)+linewidth(0.7));<br /> currentprojection=obliqueX;<br /> <br /> triple A=(0.5,0,0),C=(0,1,1),D=(0.5,1,0.5),B=(0,0,0.5);<br /> draw((0.5,0,0)--(0,0,0)--(0,0,1)--(0,0,0)--(0,1,0),linetype(&quot;4 4&quot;));<br /> draw((0.5,0,1)--(0,0,1)--(0,1,1)--(0.5,1,1)--(0.5,0,1)--(0.5,0,0)--(0.5,1,0)--(0.5,1,1));<br /> draw((0.5,1,0)--(0,1,0)--(0,1,1));<br /> dot((0.5,0,0));<br /> label(&quot;$A$&quot;,A,WSW);<br /> dot((0,1,1));<br /> label(&quot;$C$&quot;,C,NNE);<br /> dot((0.5,1,0.5));<br /> label(&quot;$D$&quot;,D,ESE);<br /> dot((0,0,0.5));<br /> label(&quot;$B$&quot;,B,NNW);<br /> draw(B--C--A--B--D,linetype(&quot;4 4&quot;));<br /> draw(A--D--C);<br /> &lt;/asy&gt;&lt;/center&gt;<br /> Since &lt;math&gt;AB = AD = CB = CD = \sqrt{.5^2+1^2}&lt;/math&gt;, it follows that &lt;math&gt;ABCD&lt;/math&gt; is a [[rhombus]]. The area of the rhombus can be computed by the formula &lt;math&gt;A = \frac 12 d_1d_2&lt;/math&gt;, where &lt;math&gt;d_1,\,d_2&lt;/math&gt; are the diagonals of the rhombus (or of a [[kite]] in general). &lt;math&gt;BD&lt;/math&gt; has the same length as a face diagonal, or &lt;math&gt;\sqrt{1^2 + 1^2} = \sqrt{2}&lt;/math&gt;. &lt;math&gt;AC&lt;/math&gt; is a space diagonal, with length &lt;math&gt;\sqrt{1^2+1^2+1^2} = \sqrt{3}&lt;/math&gt;. Thus &lt;math&gt;A = \frac 12 \times \sqrt{2} \times \sqrt{3} = \frac{\sqrt{6}}{2}\ \mathrm{(A)}&lt;/math&gt;.<br /> <br /> ==See also==<br /> {{AMC10 box|year=2008|ab=A|num-b=20|num-a=22}}<br /> <br /> [[Category:Introductory Geometry Problems]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Division_Algorithm&diff=27089 Talk:Division Algorithm 2008-07-18T16:00:34Z <p>Fedja: </p> <hr /> <div>What's currently on this page should be on the page [[Division Theorem]]. The page Division Algorithm should contain algorithms for doing division. --[[User:JBL|JBL]] 20:07, 17 July 2008 (UTC)<br /> <br /> I wonder if this page makes any sense at all then. What is supposed to be here: explanation of how to divide &lt;math&gt;12345&lt;/math&gt; by &lt;math&gt;67&lt;/math&gt;, explanation of how the computers do it in binary, some fast algorithms for very high precision computations, or what? [[User:Fedja|Fedja]] 16:00, 18 July 2008 (UTC)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Help&diff=27046 Asymptote: Help 2008-07-15T21:46:27Z <p>Fedja: /* Troubleshooting */ Added one common problem</p> <hr /> <div>{{Asymptote}}<br /> <br /> ==Troubleshooting==<br /> '''Problem 1:''' You have added the Asymptote tool to TeXnicCenter, but when you hit your hotkey, you get an 'Cannot execute the command' error. <br /> <br /> '''What might be going on:''' TeXnicCenter doesn't see the Asymptote executable.<br /> <br /> '''Possible Solution:''' Go back to the Tools -&gt; Customize window (click Tools, then Customize in TeXnicCenter). Then, click the Tools tab, then select Asymptote. Instead of cutting and pasting the text for the Command line, click the ... button after the Command entry box. Then, navigate to the asy.exe executable. You'll probably have to go up several levels to C:, then click Program Files, then Asymptote, then the file asy with the stylized red A next to it.<br /> <br /> <br /> '''Problem 2:''' I have everything installed and the hotkey doesn't give me an error in TeXnicCenter, but when I hit the hotkey to compile my code, all that happens is that a window flashes briefly then disappears. Nothing else seems to happen.<br /> <br /> '''What might be going on:''' Your file is saved as a .tex file, not a .asy file. (TeXnicCenter will even make it look like it's an .asy file, but it's really saved as an .asy.tex file.)<br /> <br /> '''Solution:''' Click file, then Save As, then type your filename with the .asy extension (such as test.asy), the set the 'Save as type' field to 'All files'. This should make it a .asy file. <br /> <br /> If this does not work then (for Windows XP) go to My Computer, Tools, Folder Options..., File Types. Click on New and type ASY, then OK. Making sure that the file type ASY is highlighted, click the Change button to the right of &quot;Opens with:&quot;. From here go to browse and find the Asymptote executable program file click Open then OK. Now, retry the File, Save As extension change method outlined above.<br /> <br /> It would also help to show file extensions so that &lt;tt&gt;file.tex, file.asy, file.pdf&lt;/tt&gt; aren't all listed in Explorer and Save boxes as &lt;tt&gt;file&lt;/tt&gt;.<br /> <br /> [http://teamtutorials.com/windows-tutorials/show-file-extension-in-windows-xp Show File Extension in Windows XP] gives a simple walkthrough to show how to do this.<br /> <br /> <br /> '''Problem 3:''' You can draw images with Asymptote, but it doesn't compile your file whenever you have a label containing LaTeX code (for example, the line &lt;tt&gt;label(&quot;&lt;math&gt;P&lt;/math&gt;&quot;,(50,50),S);&lt;/tt&gt; as in test.asy.)<br /> <br /> '''What might be going on:''' Either Asymptote is not finding your LaTeX compiler, or you have installed your TeX distribution (such as MikTeX) in a folder that Asymptote cannot find.<br /> <br /> '''Solution:''' Let's say you installed miktex in the folder &lt;tt&gt;C:\Program Files\MiKTeX 2.6&lt;/tt&gt; (the default). (If you have a different version of MiKTeX, change the 2.6 to the appropriate number. Look in C:\Program Files for the MiKTeX directory to see what this number should be.) Then there should be a subfolder miktex, containing the folder bin, which contains your latex compiler. <br /> When Asymptote is run, it looks for a file called config.asy in the folder <br /> &lt;tt&gt;C:\Documents and Settings\%USERNAME%\.asy\&lt;/tt&gt; <br /> where &lt;tt&gt;%USERNAME%&lt;/tt&gt; is your Windows user name. (In Windows Vista, this folder is &lt;tt&gt;C:\Users\%USERNAME%\.asy\&lt;/tt&gt;, where &lt;tt&gt;%USERNAME%&lt;/tt&gt; is your Windows username.) <br /> Double-click on the .asy folder, right click and choose New &lt;math&gt;\rightarrow&lt;/math&gt; Text Document. This will create a file called New Text Document.txt. Right-click on this file to rename it as config.asy, then open this file with Notepad or a similar editor. Type or copy-and-paste the following lines into the document:<br /> import settings;<br /> texpath=&quot;C:\Program Files\MiKTeX 2.6\miktex\bin&quot;;<br /> dvips=&quot;C:\Program Files\MiKTeX 2.6\miktex\bin\dvips&quot;;<br /> When you have finished, save the file config.asy.<br /> <br /> As mentioned in the solution to Problem 1, you must make sure that the config.asy file is an ASY file, and not a TXT file that is named config.asy. Look in the File Type column in the Details view to see what type of file config.asy is. If your regular text editor insists on making config.asy a TXT document, use TeXnicCenter to create config.asy.<br /> <br /> <br /> '''Problem 4:''' You run Asymptote and get &lt;tt&gt;error: could not load module 'plain'&lt;/tt&gt;. <br /> <br /> '''What might be going on:''' Asymptote cannot find the files it needs to run. It may need telling which directory it is installed in.<br /> <br /> '''Solution:''' You need to create or edit the config.asy file. See the solution to Problem 3 for how to find or create it. Assuming that Asymptote is installed at &lt;tt&gt;C:\Program Files\Asymptote&lt;/tt&gt; then<br /> <br /> a) if you already have a config.asy file add the following line somewhere after &quot;import settings;&quot;: <br /> dir=&quot;C:\Program Files\Asymptote&quot;;<br /> ''or''<br /> <br /> b) if you have created a new config.asy file then add the following lines:<br /> import settings;<br /> dir=&quot;C:\Program Files\Asymptote&quot;;<br /> <br /> See the note at the end of Problem 3 regarding creating config.asy.<br /> <br /> '''Problem 5:''' Asymptote suddenly starts misbehaving giving strange errors, going into infinite loops, and not recognizing standard package commands.<br /> <br /> '''What might be going on:''' A file with the same name as one of the standard package files (like graph.asy or math.asy) was created either by you or by &lt;math&gt;\LaTeX&lt;/math&gt; in your working directory or some other directory which Asymptote searches before going to its own directory, so that file is imported instead of the package file.<br /> <br /> '''Prevention:''' Never name your asy or tex files graph.asy, math.tex and such (these two names seem to be the most common)<br /> <br /> '''Solution:''' Find all extra files with the same name as standard packages and either .asy or .tex extension and rename or delete them.<br /> <br /> ==External Sources==<br /> The following are excellent resources on Asymptote for topics not covered in this guide:<br /> <br /> *[http://asymptote.sourceforge.net The Asymptote home page]<br /> * [http://asymptote.sourceforge.net/doc/ Asymptote documentation]<br /> * [http://asymptote.sourceforge.net/FAQ/ Asymptote FAQ]<br /> * [http://sourceforge.net/forum/forum.php?forum_id=409349 Asymptote forum]<br /> <br /> [[Asymptote: Useful functions|Next: Useful functions]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Geometric_mean&diff=27022 Geometric mean 2008-07-12T02:04:53Z <p>Fedja: removed a wrong statement</p> <hr /> <div>The '''geometric mean''' of a collection of &lt;math&gt;n&lt;/math&gt; [[positive]] [[real number]]s is the &lt;math&gt;n&lt;/math&gt;th [[root]] of the product of the numbers. Note that if &lt;math&gt;n&lt;/math&gt; is even, we take the positive &lt;math&gt;n&lt;/math&gt;th root. It is analogous to the [[arithmetic mean]] (with addition replaced by multiplication) in the following sense: the arithmetic mean of two numbers &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; is the number &lt;math&gt;a&lt;/math&gt; such that &lt;math&gt;a + a = b + c&lt;/math&gt;, while the geometric mean of the numbers &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; is the number &lt;math&gt;g&lt;/math&gt; such that &lt;math&gt;g\cdot g = b\cdot c&lt;/math&gt;.<br /> <br /> == Examples ==<br /> The geometric mean of the numbers 6, 4, 1 and 2 is &lt;math&gt;\sqrt{6\cdot 4\cdot 1 \cdot 2} = \sqrt{48} = 2\sqrt{3}&lt;/math&gt;.<br /> <br /> The geometric mean features prominently in the [[Arithmetic Mean-Geometric Mean Inequality]].<br /> <br /> The geometric mean arises in [[geometry]] in the following situation: if &lt;math&gt;AB&lt;/math&gt; is a [[chord]] of [[circle]] &lt;math&gt;O&lt;/math&gt; with [[midpoint]] &lt;math&gt;M&lt;/math&gt; and &lt;math&gt;M&lt;/math&gt; divides the [[diameter]] passing through it into pieces of length &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; then the length of [[line segment]] &lt;math&gt;AM&lt;/math&gt; is the geometric mean of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> size(150);<br /> pointfontsize=8;<br /> pathfontsize=8;<br /> pair A=(3,4),B=(3,-4),M=(3,0);<br /> D((-5,0)--(5,0)); D(M--B); <br /> MC(&quot;\sqrt{ab}&quot;,D(A--M,orange+linewidth(1)),W);<br /> MC(&quot;a&quot;,D((-5,-0.3)--(3,-0.3),black,Arrows),S);<br /> MC(&quot;b&quot;,D((3,-0.3)--(5,-0.3),black,Arrows),S);<br /> D(CR(D((0,0)),5));<br /> D(&quot;A&quot;,A,N); D(&quot;B&quot;,B);D(&quot;M&quot;,M,NE);<br /> &lt;/asy&gt;<br /> <br /> == Practice Problems ==<br /> ===Introductory Problems===<br /> * [[1966 AHSME Problems/Problem 3]]<br /> <br /> == See Also ==<br /> *[[Arithmetic Mean]]<br /> *[[AM-GM]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Vector&diff=24490 Vector 2008-04-03T00:32:55Z <p>Fedja: /* Addition of Vectors */</p> <hr /> <div>The word '''vector''' has many different definitions, depending on who is defining it and in what context. Physicists will often refer to a vector as &quot;a quantity with a direction and magnitude.&quot; For Euclidean geometers, a vector is essentially a directed line segment. In many situations, a vector is best considered as an n-tuple of numbers (often real or complex). Most generally, but also most abstractly, a vector is any object which is an element of a given vector space. <br /> <br /> A vector is usually graphically represented as an arrow. Vectors can be uniquely described in many ways. The two most common is (for 2-dimensional vectors) by describing it with its length (or magnitude) and the angle it makes with some fixed line (usually the x-axis) or by describing it as an arrow beginning at the origin and ending at the pint &lt;math&gt;(x,y)&lt;/math&gt;. An &lt;math&gt;n&lt;/math&gt;-dimensional vector can be described in this coordinate form as an ordered &lt;math&gt;n&lt;/math&gt;-tuple of numbers within angle brackets or parentheses, &lt;math&gt;(x\,\,y\,\,z\,\,...)&lt;/math&gt;. The set of vectors over a [[field]] is called a [[vector space]].<br /> <br /> == Description ==<br /> Every vector &lt;math&gt;\vec{PQ}&lt;/math&gt; has a starting point &lt;math&gt;P\langle x_1, y_1\rangle&lt;/math&gt; and an endpoint &lt;math&gt;Q\langle x_2, y_2\rangle&lt;/math&gt;. Since the only thing that distinguishes one vector from another is its magnitude,i.e. length, and direction, vectors can be freely translated about a plane without changing them. Hence, it is convenient to consider a vector as originating from the origin. This way, two vectors can be compared only by looking at their endpoints. This is why we only require &lt;math&gt;n&lt;/math&gt; values for an &lt;math&gt;n&lt;/math&gt; dimensional vector written in the form &lt;math&gt;(x\,\,y\,\,z\,\,...)&lt;/math&gt;. The magnitude of a vector, denoted &lt;math&gt;||\vec{v}||&lt;/math&gt;, is found simply by <br /> using the distance formula.<br /> <br /> == Addition of Vectors ==<br /> For vectors &lt;math&gt;\vec{v}&lt;/math&gt; and &lt;math&gt;\vec{w}&lt;/math&gt;, with angle &lt;math&gt;\theta&lt;/math&gt; formed by them, &lt;math&gt;|(\vec{v}+\vec{w})|^2=|\vec{v}|^2+|\vec{w}|^2+2|\vec{v}||\vec{w}|\cos\theta&lt;/math&gt;.<br /> {{asy image|&lt;asy&gt; <br /> size(150);<br /> pen p=linewidth(1);<br /> MA(&quot;\theta&quot;,(5,-1),(2,3),(4,6),0.3,9,yellow);<br /> MC(&quot;\vec v&quot;,D((0,0)--(2,3),orange+p,Arrow),NW);<br /> D((2,3)--(3,4.5));<br /> MC(&quot;\vec w&quot;,D((2,3)--(5,-1),green+p,Arrow),NE);<br /> MC(-10,&quot;\vec{v}+\vec{w}&quot;,D((0,0)--(5,-1),red+p,Arrow),S);<br /> &lt;/asy&gt;|right|Addition of vectors}}<br /> <br /> From this it is simple to derive that for a real number &lt;math&gt;c&lt;/math&gt;, &lt;math&gt;c\vec{v}&lt;/math&gt; is the vector &lt;math&gt;\vec{v}&lt;/math&gt; with magnitude multiplied by &lt;math&gt;c&lt;/math&gt;. Negative &lt;math&gt;c&lt;/math&gt; corresponds to opposite directions.<br /> <br /> == Properties of Vectors ==<br /> Since a [[vector space]] is defined over a [[field]] &lt;math&gt;K&lt;/math&gt;, it is logically inherent that vectors have the same properties as those elements in a field.<br /> <br /> For any vectors &lt;math&gt;\vec{x}&lt;/math&gt;, &lt;math&gt;\vec{y}&lt;/math&gt;, &lt;math&gt;\vec{z}&lt;/math&gt;, and real numbers &lt;math&gt;a,b&lt;/math&gt;,<br /> <br /> #&lt;math&gt;\vec{x}+\vec{y}=\vec{y}+\vec{x}&lt;/math&gt; ([[Commutative]] in +)<br /> #&lt;math&gt;(\vec{x}+\vec{y})+\vec{z}=\vec{x}+(\vec{y}+\vec{z})&lt;/math&gt; ([[Associative]] in +)<br /> #There exists the zero vector &lt;math&gt;\vec{0}&lt;/math&gt; such that &lt;math&gt;\vec{x}+\vec{0}=\vec{x}&lt;/math&gt; ([[Additive identity]])<br /> #For each &lt;math&gt;\vec{x}&lt;/math&gt;, there is a vector &lt;math&gt;\vec{y}&lt;/math&gt; such that &lt;math&gt;\vec{x}+\vec{y}=\vec{0}&lt;/math&gt; ([[Additive inverse]])<br /> #&lt;math&gt;1\vec{x}=\vec{x}&lt;/math&gt; (Unit scalar identity)<br /> #&lt;math&gt;(ab)\vec{x}=a(b\vec{x})&lt;/math&gt; ([[Associative]] in scalar)<br /> #&lt;math&gt;a(\vec{x}+\vec{y})=a\vec{x}+a\vec{y}&lt;/math&gt; ([[Distributive]] on vectors)<br /> #&lt;math&gt;(a+b)\vec{x}=a\vec{x}+b\vec{x}&lt;/math&gt; ([[Distributive]] on scalars)<br /> <br /> == Vector Operations ==<br /> ===Dot (Scalar) Product===<br /> Consider two vectors &lt;math&gt;\bold{u}=\langle u_1,u_2,\ldots,u_n\rangle&lt;/math&gt; and &lt;math&gt;\bold{v}=\langle v_1, v_2,\ldots,v_n\rangle&lt;/math&gt; in &lt;math&gt;\mathbb{R}^n&lt;/math&gt;. The dot product is defined as &lt;math&gt;\bold{u}\cdot\bold{v}=u_1v_1+u_2v_2+\cdots+u_nv_n&lt;/math&gt;.<br /> <br /> ===Cross (Vector) Product===<br /> The cross product between two vectors &lt;math&gt;\bold{a}&lt;/math&gt; and &lt;math&gt;\bold{b}&lt;/math&gt; in &lt;math&gt;\mathbb{R}^3&lt;/math&gt; is defined as the vector whose length is equal to the area of the parallelogram spanned by &lt;math&gt;\bold{a}&lt;/math&gt; and &lt;math&gt;\bold{b}&lt;/math&gt; and whose direction is in accordance with the [[right-hand rule]].<br /> <br /> If &lt;math&gt;\vec{a}=\langle a_1,a_2,a_3\rangle&lt;/math&gt; and &lt;math&gt;\vec{b}=\langle b_1,b_2,b_3\rangle&lt;/math&gt;, then the cross product of &lt;math&gt;\vec{a}&lt;/math&gt; and &lt;math&gt;\vec{b}&lt;/math&gt; is given by <br /> &lt;center&gt;&lt;math&gt;\vec{a}\times\vec{b}=\begin{vmatrix} \hat{i} &amp; \hat{j} &amp; \hat{k} \\ a_1 &amp; a_2 &amp; a_3 \\ b_1 &amp; b_2 &amp; b_3\end{vmatrix}.&lt;/math&gt;&lt;/center&gt;<br /> where &lt;math&gt;\hat{i},\hat{j},\hat{k}&lt;/math&gt; are [[unit vector]]s along the co-ordinate axes.<br /> <br /> ===Triple Scalar Product===<br /> The triple scalar product of three vectors &lt;math&gt;\bold{a,b,c}&lt;/math&gt; is defined as &lt;math&gt;(\bold{a}\times\bold{b})\cdot \bold{c}&lt;/math&gt;. Geometrically, the triple scalar product gives the signed area of the parallelpiped determined by &lt;math&gt;\bold{a,b}&lt;/math&gt; and &lt;math&gt;\bold{c}&lt;/math&gt;. It follows that <br /> <br /> &lt;center&gt;&lt;math&gt;(\bold{a}\times\bold{b})\cdot \bold{c} = (\bold{c}\times\bold{a})\cdot \bold{b} = (\bold{b}\times\bold{c})\cdot \bold{a}.&lt;/math&gt;&lt;/center&gt;<br /> <br /> It can also be shown that <br /> <br /> &lt;center&gt;&lt;math&gt;(\bold{a}\times\bold{b})\cdot \bold{c} = \begin{vmatrix} a_1 &amp; a_2 &amp; a_3 \\ b_1 &amp; b_2 &amp; b_3 \\ c_1 &amp; c_2 &amp; c_3 \end{vmatrix}.&lt;/math&gt;&lt;/center&gt;<br /> <br /> ===Triple Vector Product===<br /> <br /> == See Also ==<br /> *[[Linear Algebra]]<br /> *[[Matrix]]<br /> *[http://www.artofproblemsolving.com/Forum/index.php?f=346\ Matrix-Linear Algebra AOPS forum]<br /> <br /> == Discussion ==<br /> *[http://www.artofproblemsolving.com/Forum/viewtopic.php?t=89911\ This is a thread about what vectors are.]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Ellipse&diff=24487 Ellipse 2008-04-03T00:13:10Z <p>Fedja: </p> <hr /> <div>An '''ellipse''' is a type of [[conic section]].<br /> <br /> ==Definition==<br /> An ellipse is formed by cutting through a [[cone]] at an [[angle]]. <br /> Equivalently, it is defined as the [[locus]], or [[set]], of all [[point]]s &lt;math&gt;P&lt;/math&gt; such that the sum of the distances from &lt;math&gt;P&lt;/math&gt; to two fixed [[focus|foci]] is a constant. (The equivalence of these two definitions is a non-trivial fact.)<br /> <br /> Ellipses tend to resemble [[circle]]s which have been &quot;flattened&quot; or &quot;stretched.&quot; They occur in nature as well as in mathematics: as was proven in [[Kepler's Laws]], the planets all revolve about the sun in elliptical, not circular, orbits with the sun at one of the foci. Note that the circle is just a special case of the ellipse, just as a square is to a rectangle, and occurs when (in the first definition) the cut is [[perpendicular]] to the axis of the the cone, or (in the second definition) the two foci of the ellipse coincide.<br /> <br /> For a given non-circular ellipse, there will be two points on the ellipse closest to the center and two points furthest away -- it will be &quot;tall and skinny&quot; or &quot;short and fat.&quot; The segment connecting the center of the ellipse to one of the &quot;farther away ends&quot; is called the ''[[semimajor axis]]'' and the segment connecting the center to a closer end is called the ''[[semiminor axis]]''. These two segments are perpendicular. Drawing all four semi-axes divides the ellipse into 4 [[congruent (geometry)|congruent]] quarters.<br /> <br /> {{asy image|<br /> &lt;asy&gt;<br /> size(200);<br /> D((-5,0)--(0,0)--(0,-3));<br /> MC(90,&quot;\mbox{semiminor axis}&quot;,7,D((0,0)--(0,3),green+linewidth(1)),E);<br /> MC(&quot;\mbox{semimajor axis}&quot;,7,D((0,0)--(5,0),red+linewidth(1)),S);<br /> D(ellipse(D(&quot;\mbox{center}&quot;,7,(0,0),black,SW),5,3),orange+linewidth(1));<br /> &lt;/asy&gt;|right|Ellipse<br /> }}<br /> <br /> Using the second definition of an ellipse given above, one may easily construct an ellipse from household materials. To draw an ellipse with two pushpins, a loop of string, pencil, and paper, stick the pushpins in the paper place the string on the paper so that both pushpins are inside it. The pushpins will be the foci of the ellipse, and the length of the string will determine the sum of the distances from a point on the ellipse to the two foci. Hold the pencil on the paper such that the string is taut against the pencil tip and the two pushpins. Then move the pencil tip while keeping the string taut. This will traces out an ellipse.<br /> <br /> An ellipse in a [[Cartesian coordinate system]] with center &lt;math&gt;C = (h, k)&lt;/math&gt; whose axes are parallel to the coordinate axes, with the vertical semi-axis of length &lt;math&gt;a&lt;/math&gt; and the horizontal semi-axis of length &lt;math&gt;b&lt;/math&gt; is given by the equation &lt;math&gt;\frac{(x-h)^2}{a^2}+\frac{(y-k)^2}{b^2}=1&lt;/math&gt;. In particular, if the center of the ellipse is the origin this simplifies to &lt;math&gt;\frac{x^2}{a^2}+\frac{y^2}{b^2}=1&lt;/math&gt;.<br /> <br /> The three-dimensional counterpart of the ellipse is the [[ellipsoid]].<br /> <br /> ==Related Formulae==<br /> *The [[area]] of an ellipse with major and minor axes &lt;math&gt;a,b&lt;/math&gt; is &lt;math&gt;ab\pi&lt;/math&gt;.<br /> *The [[circumference]] of an ellipse is &lt;math&gt;4aE(\epsilon)&lt;/math&gt;, where the &lt;math&gt;E&lt;/math&gt; is the second [[elliptic integral]].<br /> <br /> ==Problems==<br /> ===Introductory===<br /> ===Intermediate===<br /> *Let &lt;math&gt; w_1 &lt;/math&gt; and &lt;math&gt; w_2 &lt;/math&gt; denote the circles &lt;math&gt; x^2+y^2+10x-24y-87=0 &lt;/math&gt; and &lt;math&gt; x^2 +y^2-10x-24y+153=0, &lt;/math&gt; respectively. Let &lt;math&gt; m &lt;/math&gt; be the smallest possible value of &lt;math&gt; a &lt;/math&gt; for which the line &lt;math&gt; y=ax &lt;/math&gt; contains the center of a circle that is externally tangent to &lt;math&gt; w_2 &lt;/math&gt; and internally tangent to &lt;math&gt; w_1. &lt;/math&gt; Given that &lt;math&gt; m^2=\frac pq, &lt;/math&gt; where &lt;math&gt; p &lt;/math&gt; and &lt;math&gt; q &lt;/math&gt; are relatively prime integers, find &lt;math&gt; p+q. &lt;/math&gt; ([[2005 AIME II Problems/Problem 15|Source]])<br /> *An equilateral triangle is inscribed in the ellipse whose equation is &lt;math&gt;x^2+4y^2=4&lt;/math&gt;. One vertex of the triangle is &lt;math&gt;(0,1)&lt;/math&gt;, one altitude is contained in the y-axis, and the length of each side is &lt;math&gt;\sqrt{\frac mn}&lt;/math&gt;, where &lt;math&gt;m&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt; are relatively prime positive integers. Find &lt;math&gt;m+n&lt;/math&gt;. ([[2001 AIME I Problems/Problem 5|Source]])<br /> *An [[ellipse]] has [[focus | foci]] at &lt;math&gt;(9,20)&lt;/math&gt; and &lt;math&gt;(49,55)&lt;/math&gt; in the &lt;math&gt;xy&lt;/math&gt;-plane and is [[tangent line | tangent]] to the &lt;math&gt;x&lt;/math&gt;-axis. What is the length of its [[major axis]]? ([[1985 AIME Problems/Problem 11|Source]])<br /> ===Olympiad===<br /> <br /> ==See also==<br /> * [[Parabola]]<br /> * [[Conic section]]s<br /> * [[Geometry]]<br /> * [[Polynomial]]s<br /> <br /> [[Category:Definition]]<br /> [[CAtegory:Geometry]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Geometric_mean&diff=24485 Geometric mean 2008-04-02T23:49:46Z <p>Fedja: </p> <hr /> <div>The '''geometric mean''' of a collection of &lt;math&gt;n&lt;/math&gt; [[positive]] [[real number]]s is the &lt;math&gt;n&lt;/math&gt;th [[root]] of the product of the numbers. Note that if &lt;math&gt;n&lt;/math&gt; is even, we take the positive &lt;math&gt;n&lt;/math&gt;th root. It is analogous to the [[arithmetic mean]] (with addition replaced by multiplication) in the following sense: the arithmetic mean of two numbers &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; is the number &lt;math&gt;a&lt;/math&gt; such that &lt;math&gt;a + a = b + c&lt;/math&gt;, while the geometric mean of the numbers &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;c&lt;/math&gt; is the number &lt;math&gt;g&lt;/math&gt; such that &lt;math&gt;g\cdot g = b\cdot c&lt;/math&gt;.<br /> <br /> == Examples ==<br /> The geometric mean of the numbers 6, 4, 1 and 2 is &lt;math&gt;\sqrt{6\cdot 4\cdot 1 \cdot 2} = \sqrt{48} = 2\sqrt{3}&lt;/math&gt;.<br /> <br /> The geometric mean features prominently in the [[Arithmetic Mean-Geometric Mean Inequality]].<br /> <br /> The geometric mean arises in [[geometry]] in the following situation: if &lt;math&gt;AB&lt;/math&gt; is a [[chord]] of [[circle]] &lt;math&gt;O&lt;/math&gt; with [[midpoint]] &lt;math&gt;M&lt;/math&gt; and &lt;math&gt;M&lt;/math&gt; divides the [[diameter]] passing through it into pieces of length &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; then the length of [[line segment]] &lt;math&gt;AM&lt;/math&gt; is the geometric mean of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> size(150);<br /> pointfontsize=8;<br /> pathfontsize=8;<br /> pair A=(3,4),B=(3,-4),M=(3,0);<br /> D((-5,0)--(5,0)); D(M--B); <br /> MC(&quot;\sqrt{ab}&quot;,D(A--M,orange+linewidth(1)),W);<br /> MC(&quot;a&quot;,D((-5,-0.3)--(3,-0.3),black,Arrows),S);<br /> MC(&quot;b&quot;,D((3,-0.3)--(5,-0.3),black,Arrows),S);<br /> D(CR(D((0,0)),5));<br /> D(&quot;A&quot;,A,N); D(&quot;B&quot;,B);D(&quot;M&quot;,M,NE);<br /> &lt;/asy&gt;<br /> <br /> The geometric mean also arises in the following common [[word problem]]: if a driver travels half the distance of a trip at a speed of &lt;math&gt;a&lt;/math&gt; miles per hour and the other half at a speed of &lt;math&gt;b&lt;/math&gt; miles per hour, the average speed over the whole trip is the geometric mean of &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;. (If the driver spent half the ''time'' of the trip at each speed, we would instead get the arithmetic mean.)<br /> <br /> == Practice Problems ==<br /> ===Introductory Problems===<br /> * [[1966 AHSME Problems/Problem 3]]<br /> <br /> == See Also ==<br /> *[[Arithmetic Mean]]<br /> *[[AM-GM]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_CSE5&diff=24464 Asymptote: CSE5 2008-04-02T19:04:44Z <p>Fedja: /* Function List */</p> <hr /> <div>{{Asymptote}}<br /> The Asymptote '''CSE5''' package is another package that is supported on the AoPS forum. The original idea for writing CSE5 was to enable writing terse codes for complicated pictures. Also some commands in CSE5 (like '''IP()''') work slightly better than the standard Asymptote routines in some cases (the typical example is finding the intersection point of a circle and a tangent line). At last, CSE5 allows to handle some runtime errors like an attempt to find an intersection point of two paths without common points, which may be useful if you try to draw a picture just from its verbal description and do not want to make any calculations beforehand.<br /> CSE5 contains doubles of each function; a function with a full name and a function with an abbreviated name. <br /> ==Function List==<br /> &lt;pre&gt;<br /> MarkPoint ( MP );<br /> MarkCurve ( MC );<br /> MarkAngle ( MA );<br /> Drawing ( D );<br /> DrawPathArray ( DPA );<br /> IntersectionPoint ( IP );<br /> OtherPoint ( OP );<br /> IntersectionPoints ( IPs );<br /> WayPoint ( WP );<br /> Line ( L );<br /> CirclebyRadius ( CR );<br /> CirclebyPoint ( CP );<br /> CopyClean ( CC );<br /> &lt;/pre&gt;<br /> <br /> ==Function descriptions==<br /> === MarkAngle ( MA ) ===<br /> pair MA(real a,Label s,int f,pen p,pair B,pair A,pair C,real r,int m,pair P,pen q)<br /> <br /> The '''MA()''' or '''MarkAngle()''' command is a competitor of the olympiad '''anglemark()'''. The usage is<br /> '''MA(''' ''a,s,f,p'','''B,A,C,r''',''m,S,q'' ''')''' <br /> (the necessary arguments are bold and the optional ones are italic). Here<br /> <br /> ''a'' is the angle by which you want to rotate the label in degrees (0 by default);<br /> <br /> ''s'' is the string labelling the angle (empty string by default); the dollar (or now rather $$...$$) delimeters will be added automatically as in other cse5 labelling commands;<br /> <br /> ''f'' is the fontsize for your label (currently 9 by default; can be also reset by the '''anglefontsize=...''' command);<br /> <br /> ''p'' is the pen you wish to use for the label (red by default; can be also reset by the '''anglefontpen=...''' command);<br /> <br /> '''B,A,C''' are the pairs determining the angle &lt;math&gt;\angle BAC&lt;/math&gt; with the vertex &lt;math&gt;A&lt;/math&gt;. The arcs are drawn counterclockwise from the side &lt;math&gt;AB&lt;/math&gt; to the side &lt;math&gt;AC&lt;/math&gt;;<br /> <br /> '''r''' the radius of the largest arc in the anglemark;<br /> <br /> ''m'' the number of arcs in the anglemark (&lt;math&gt;1&lt;/math&gt; by default). Can be set to &lt;math&gt;0&lt;/math&gt;, in which case no arcs will be drawn, &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;7&lt;/math&gt;, in which case &lt;math&gt;m&lt;/math&gt; arcs will be drawn, and anything &lt;math&gt;&gt;7&lt;/math&gt; in which case the sector will be filled with color;<br /> <br /> ''S'' allows you to position the label manually with respect to the middle point of the largest arc. The automatic positioning is where you, probably, want it to be the most: on the bisector of the angle right beyond the largest arc in the anglemark.<br /> <br /> ''q'' is the pen used for drawing the arcs or filling the sector (green by default; can be also reset by the '''anglepen=...''' command).<br /> <br /> '''MA()''' returns the vertex of the angle.<br /> <br /> Example of usage:<br /> &lt;pre&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/pre&gt; <br /> results in<br /> &lt;asy&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/asy&gt;<br /> <br /> == See Also ==<br /> *&lt;url&gt;viewtopic.php?t=149650 Description of the package&lt;/url&gt; by [[AoPS]] user [[User:fedja|fedja]].</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_CSE5&diff=24463 Asymptote: CSE5 2008-04-02T18:56:37Z <p>Fedja: </p> <hr /> <div>{{Asymptote}}<br /> The Asymptote '''CSE5''' package is another package that is supported on the AoPS forum. The original idea for writing CSE5 was to enable writing terse codes for complicated pictures. Also some commands in CSE5 (like '''IP()''') work slightly better than the standard Asymptote routines in some cases (the typical example is finding the intersection point of a circle and a tangent line). At last, CSE5 allows to handle some runtime errors like an attempt to find an intersection point of two paths without common points, which may be useful if you try to draw a picture just from its verbal description and do not want to make any calculations beforehand.<br /> CSE5 contains doubles of each function; a function with a full name and a function with an abbreviated name. <br /> ==Function List==<br /> === Mark Angle ( MA ) ===<br /> pair MA(real a,Label s,int f,pen p,pair B,pair A,pair C,real r,int m,pair P,pen q)<br /> <br /> The '''MA()''' or '''MarkAngle()''' command is a competitor of the olympiad '''anglemark()'''. The usage is<br /> '''MA(''' ''a,s,f,p'','''B,A,C,r''',''m,S,q'' ''')''' <br /> (the necessary arguments are bold and the optional ones are italic). Here<br /> <br /> ''a'' is the angle by which you want to rotate the label in degrees (0 by default);<br /> <br /> ''s'' is the string labelling the angle (empty string by default); the dollar (or now rather $$...$$) delimeters will be added automatically as in other cse5 labelling commands;<br /> <br /> ''f'' is the fontsize for your label (currently 9 by default; can be also reset by the '''anglefontsize=...''' command);<br /> <br /> ''p'' is the pen you wish to use for the label (red by default; can be also reset by the '''anglefontpen=...''' command);<br /> <br /> '''B,A,C''' are the pairs determining the angle &lt;math&gt;\angle BAC&lt;/math&gt; with the vertex &lt;math&gt;A&lt;/math&gt;. The arcs are drawn counterclockwise from the side &lt;math&gt;AB&lt;/math&gt; to the side &lt;math&gt;AC&lt;/math&gt;;<br /> <br /> '''r''' the radius of the largest arc in the anglemark;<br /> <br /> ''m'' the number of arcs in the anglemark (&lt;math&gt;1&lt;/math&gt; by default). Can be set to &lt;math&gt;0&lt;/math&gt;, in which case no arcs will be drawn, &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;7&lt;/math&gt;, in which case &lt;math&gt;m&lt;/math&gt; arcs will be drawn, and anything &lt;math&gt;&gt;7&lt;/math&gt; in which case the sector will be filled with color;<br /> <br /> ''S'' allows you to position the label manually with respect to the middle point of the largest arc. The automatic positioning is where you, probably, want it to be the most: on the bisector of the angle right beyond the largest arc in the anglemark.<br /> <br /> ''q'' is the pen used for drawing the arcs or filling the sector (green by default; can be also reset by the '''anglepen=...''' command).<br /> <br /> '''MA()''' returns the vertex of the angle.<br /> <br /> Example of usage:<br /> &lt;pre&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/pre&gt; <br /> results in<br /> &lt;asy&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/asy&gt;<br /> <br /> == See Also ==<br /> *&lt;url&gt;viewtopic.php?t=149650 Description of the package&lt;/url&gt; by [[AoPS]] user [[User:fedja|fedja]].</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_CSE5&diff=24462 Asymptote: CSE5 2008-04-02T18:45:02Z <p>Fedja: /* Mark Angle ( MA ) */</p> <hr /> <div>{{Asymptote}}<br /> The Asymptote '''CSE5''' package is a useful package that is supported on the AoPS forum. It is much larger than most other packages, and contains doubles of each function; a function with a full name and a function with an abbreviated name.<br /> ==Function List==<br /> === Mark Angle ( MA ) ===<br /> pair MA(real a,Label s,int f,pen p,pair B,pair A,pair C,real r,int m,pair P,pen q)<br /> <br /> The '''MA()''' or '''MarkAngle()''' command is a competitor of the olympiad '''anglemark()'''. The usage is<br /> '''MA(''' ''a,s,f,p'','''B,A,C,r''',''m,S,q'' ''')''' <br /> (the necessary arguments are bold and the optional ones are italic). Here<br /> <br /> ''a'' is the angle by which you want to rotate the label in degrees (0 by default);<br /> <br /> ''s'' is the string labelling the angle (empty string by default); the dollar (or now rather $$...$$) delimeters will be added automatically as in other cse5 labelling commands;<br /> <br /> ''f'' is the fontsize for your label (currently 9 by default; can be also reset by the '''anglefontsize=...''' command);<br /> <br /> ''p'' is the pen you wish to use for the label (red by default; can be also reset by the '''anglefontpen=...''' command);<br /> <br /> '''B,A,C''' are the pairs determining the angle &lt;math&gt;\angle BAC&lt;/math&gt; with the vertex &lt;math&gt;A&lt;/math&gt;. The arcs are drawn counterclockwise from the side &lt;math&gt;AB&lt;/math&gt; to the side &lt;math&gt;AC&lt;/math&gt;;<br /> <br /> '''r''' the radius of the largest arc in the anglemark;<br /> <br /> ''m'' the number of arcs in the anglemark (&lt;math&gt;1&lt;/math&gt; by default). Can be set to &lt;math&gt;0&lt;/math&gt;, in which case no arcs will be drawn, &lt;math&gt;1&lt;/math&gt; through &lt;math&gt;7&lt;/math&gt;, in which case &lt;math&gt;m&lt;/math&gt; arcs will be drawn, and anything &lt;math&gt;&gt;7&lt;/math&gt; in which case the sector will be filled with color;<br /> <br /> ''S'' allows you to position the label manually with respect to the middle point of the largest arc. The automatic positioning is where you, probably, want it to be the most: on the bisector of the angle right beyond the largest arc in the anglemark.<br /> <br /> ''q'' is the pen used for drawing the arcs or filling the sector (green by default; can be also reset by the '''anglepen=...''' command).<br /> <br /> '''MA()''' returns the vertex of the angle.<br /> <br /> Example of usage:<br /> &lt;pre&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/pre&gt; <br /> results in<br /> &lt;asy&gt;<br /> size(200);<br /> pair A=dir(-40), B=dir(0);<br /> for(int k=0;k&lt;9;++k)<br /> {<br /> pair C=dir(40*(k+1));<br /> D(A--D(MA(k*40+90,&quot;\beta_{&quot;+string(k)+&quot;}&quot;,12,black,C,B,A,0.1,k,orange))--C);<br /> A=B;B=C;<br /> }<br /> &lt;/asy&gt;<br /> <br /> == See Also ==<br /> *&lt;url&gt;viewtopic.php?t=149650 Description of the package&lt;/url&gt; by [[AoPS]] user [[User:fedja|fedja]].</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Pascal%27s_Theorem&diff=24342 Pascal's Theorem 2008-03-28T16:03:34Z <p>Fedja: added a picture</p> <hr /> <div>{{WotWAnnounce|week=March 20-27}}<br /> '''Pascal's Theorem''' is a result in [[projective geometry]]. It states that if a [[hexagon]] inscribed in a [[conic section]], then the points of intersection of the pairs of its opposite sides are collinear:<br /> &lt;asy&gt;<br /> size(250);<br /> D(unitcircle,red);<br /> pair A=dir(20), B=dir(40), <br /> C=dir(70), D=dir(120),<br /> E=dir(210),F=dir(300);<br /> D(L(D(IP(D(L(A,B,0.5,7)),D(L(E,D,0.5,1.5)))),<br /> D(IP(D(L(C,B,0.5,10)),D(L(E,F,0.5,3.3)))),0.1),dashed);<br /> D(IP(D(L(A,F,1,0.5)),D(L(C,D,2,0.5)))); <br /> D(A--B--C--D--E--F--A,black+linewidth(1)); <br /> &lt;/asy&gt;<br /> Since it is a result in the projective plane, it has a dual, [[Brianchon's Theorem]], which states that the diagonals of a hexagon circumscribed about a conic concur.<br /> <br /> == Proof ==<br /> <br /> It is sufficient to prove the result for a hexagon inscribed in a circle, for [[affine transformations]] map this circle to any ellipse while preserving collinearity and concurrence in the projective plane, and projective transformations can map an ellipse to any conic while similarly preserving collinearity and concurrence in the projective sense. Thus we will prove the theorem for a cyclic hexagon, using directed angles mod &lt;math&gt;\pi &lt;/math&gt;.<br /> <br /> '''Lemma.''' Let &lt;math&gt;\omega_1, \omega_2 &lt;/math&gt; be two circles which intersect at &lt;math&gt;M, N &lt;/math&gt;, let &lt;math&gt;AB &lt;/math&gt; be a chord of &lt;math&gt;\omega_1 &lt;/math&gt;, and let &lt;math&gt;C, D &lt;/math&gt; be the second intersections of lines &lt;math&gt;AM, BN &lt;/math&gt; with &lt;math&gt;\omega_2 &lt;/math&gt;. Then &lt;math&gt;AB &lt;/math&gt; and &lt;math&gt;CD &lt;/math&gt; are parallel.<br /> <br /> ''Proof.'' Since &lt;math&gt;ABNM, CDMN &lt;/math&gt; are two sets of concyclic points and &lt;math&gt;A,M,C &lt;/math&gt; and &lt;math&gt;B,N,D &lt;/math&gt; are two sets of collinear points,<br /> &lt;center&gt;<br /> &lt;math&gt; \angle CAB \equiv \angle MAB \equiv \angle MNB \equiv \angle MND \equiv \angle MCD \equiv \angle ACD &lt;/math&gt;.<br /> &lt;/center&gt;<br /> This implies that &lt;math&gt;AB &lt;/math&gt; and &lt;math&gt;CD &lt;/math&gt; are parallel. {{Halmos}}<br /> <br /> '''Theorem.''' Let &lt;math&gt;A_1A_2A_3A_4A_5A_6 &lt;/math&gt; be a cyclic hexagon, and let &lt;math&gt; P_1 = A_1A_2 \cap A_4A_5 &lt;/math&gt;, &lt;math&gt; P_2 = A_2A_3 \cap A_5A_6 &lt;/math&gt;, &lt;math&gt; P_3 = A_3A_4 \cap A_6A_1 &lt;/math&gt;. Then &lt;math&gt;P_1, P_2, P_3 &lt;/math&gt; are collinear.<br /> <br /> ''Proof.'' Let &lt;math&gt;\omega_1 &lt;/math&gt; be the circumcircle of &lt;math&gt;A_1A_2A_3A_4A_5A_6 &lt;/math&gt;, and let &lt;math&gt;\omega_2 &lt;/math&gt; be the circumcircle of triangle &lt;math&gt;A_2A_5P_2 &lt;/math&gt;. Let &lt;math&gt;B_1 &lt;/math&gt; be the second intersection of &lt;math&gt;\omega_2 &lt;/math&gt; with &lt;math&gt;A_1A_2 &lt;/math&gt;, and let &lt;math&gt;B_2 &lt;/math&gt; be the second intersection of &lt;math&gt;A_4A_5 &lt;/math&gt; with &lt;math&gt;\omega_2 &lt;/math&gt;. By lemma, &lt;math&gt;A_1P_3 = A_1A_6 &lt;/math&gt; is parallel to &lt;math&gt;B_1P_2 &lt;/math&gt;, and &lt;math&gt;A_1A_4 &lt;/math&gt; is parallel to &lt;math&gt;B_1B_2 &lt;/math&gt;, and &lt;math&gt;P_3A_4 = A_4A_3 &lt;/math&gt; is parallel to &lt;math&gt;P_2B_2 &lt;/math&gt;. It follows that triangles &lt;math&gt;P_3A_1A_4 &lt;/math&gt; and &lt;math&gt;P_2B_1B_2 &lt;/math&gt; are homothetic, so the line &lt;math&gt;P_3P_2 &lt;/math&gt; passes through the intersection of lines &lt;math&gt;A_1B_1 &lt;/math&gt; (which is the same as line &lt;math&gt;A_1A_2 &lt;/math&gt;) and &lt;math&gt;A_4B_2 &lt;/math&gt; (which is the same as line &lt;math&gt;A_4A_5 &lt;/math&gt;), which interesect at &lt;math&gt;P_1 &lt;/math&gt;. {{halmos}}<br /> <br /> == Notes ==<br /> <br /> In our proof, we never assumed anything about configuration. Thus the hexagon need not even be convex for the theorem to hold. In fact, many useful applications of the theorem occur with degenerate hexagons, i.e., hexagons in which not all of the points are distinct. In the case that two points are the same, we consider the line through them to be the tangent to the conic through that point. For instance, when we let a triangle &lt;math&gt;ABC &lt;/math&gt; be a &quot;hexagon&quot; &lt;math&gt;AABBCC &lt;/math&gt;, Pascal's Theorem tells us that if &lt;math&gt; \ell_A, \ell_B, \ell_C &lt;/math&gt; are the tangents to the circumcircle of &lt;math&gt;ABC &lt;/math&gt; that pass through &lt;math&gt;A,B,C &lt;/math&gt;, respectively, then &lt;math&gt; \ell_A \cap BC &lt;/math&gt;, &lt;math&gt; \ell_B \cap CA &lt;/math&gt;, &lt;math&gt; \ell_C \cap AB &lt;/math&gt; are collinear; the line they determine is called the [[Lemoine Axis]]. In fact, Pascal's Theorem tells us that &lt;math&gt; \ell_A, \ell_B, \ell_C &lt;/math&gt; can be the tangent lines to any conic circumscribed about triangle &lt;math&gt;ABC &lt;/math&gt; and the result still holds.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Useful_commands_and_their_Output&diff=24320 Asymptote: Useful commands and their Output 2008-03-27T00:53:04Z <p>Fedja: </p> <hr /> <div>{{Asymptote}}<br /> <br /> For each of the following, we have put a blue dot at the origin in order to indicate relative location of the output on the coordinate plane. In other words, assume that before each of the examples below is the command <br /> &lt;tt&gt;dot((0,0),blue);&lt;/tt&gt;<br /> In addition, a comment after a line such as &lt;tt&gt;//math - extension&lt;/tt&gt; indicates that the command (in this case &lt;tt&gt;extension&lt;/tt&gt;) used in that line is defined in the &lt;tt&gt;math&lt;/tt&gt; package, thus motivating the &lt;tt&gt;import math;&lt;/tt&gt; (or other appropriate package) line at the top of the example.<br /> <br /> ----<br /> <br /> '''Example 1:'''<br /> dot((20,0));<br /> '''Output 1:'''<br /> &lt;asy&gt;dot((20,0));&lt;/asy&gt;<br /> <br /> ----<br /> <br /> '''Example 2:'''<br /> draw((0,0)--(50,0),BeginArrow);<br /> draw((0,-10)--(50,-10),MidArrow);<br /> draw((0,-20)--(50,-20),EndArrow);<br /> draw((0,-30)--(50,-30),Arrows);<br /> '''Output 2:'''<br /> &lt;asy&gt; size(75);draw((0,0)--(50,0),BeginArrow);<br /> draw((0,-10)--(50,-10),MidArrow);<br /> draw((0,-20)--(50,-20),EndArrow);<br /> draw((0,-30)--(50,-30),Arrows);&lt;/asy&gt;<br /> <br /> ----<br /> <br /> '''Example 3:'''<br /> draw((0,0)--(50,0));<br /> arrow((30,0),dir(180),green);<br /> '''Output 3:'''<br /> [[Image:Figure4.gif]]<br /> <br /> ----<br /> <br /> '''Example 4:'''<br /> import math;<br /> pair A,B,C,D,E;<br /> A=(0,0); C=(50,0); B=(10,10); D=(40,20);<br /> E=extension(A,B,C,D); // math - extension<br /> // extension(A,B,C,D) returns the intersection of lines AB and CD<br /> draw(A--B); draw(C--D);<br /> draw(B--E--D,orange);<br /> <br /> '''Output 4:'''<br /> [[Image:Figure5.gif]]<br /> <br /> ----<br /> <br /> '''Example 5:'''<br /> import graph;<br /> draw(Circle((0,0),20)); // graph - Circle<br /> '''Output 5:'''<br /> [[Image:Figure6.gif]]<br /> <br /> ----<br /> <br /> '''Example 6:'''<br /> path p=(0,0)..(20,15)..(40,-5)..(50,0);<br /> draw(p);<br /> draw(rotate(90)*p,green);<br /> draw(rotate(180,(-5,0))*p,orange);<br /> draw(shift((5,20))*p,magenta);<br /> draw(shift((0,-25))*yscale(1.4)*p,red);<br /> <br /> '''Output 6:'''<br /> [[Image:Figure7.gif]]<br /> <br /> ----<br /> <br /> '''Example 7:'''<br /> &lt;pre&gt;&lt;nowiki&gt;<br /> import olympiad;<br /> unitsize(50);<br /> pair A,B,C,O,I;<br /> A=origin; B=2*right; C=1.5*dir(70);<br /> O=circumcenter(A,B,C); // olympiad - circumcenter<br /> I=incenter(A,B,C); // olympiad - incenter<br /> draw(A--B--C--cycle);<br /> dot(O);<br /> dot(I);<br /> draw(circumcircle(A,B,C)); // olympiad - circumcircle<br /> draw(incircle(A,B,C)); // olympiad - incircle<br /> label(&quot;$I$&quot;,I,W);<br /> label(&quot;$O$&quot;,O,S);<br /> &lt;/nowiki&gt;&lt;/pre&gt;<br /> <br /> '''Output 7:'''<br /> &lt;asy&gt;<br /> import olympiad;<br /> size(75);<br /> pair A,B,C,O,I;<br /> A=origin; B=2*right; C=1.5*dir(70);<br /> O=circumcenter(A,B,C); /* olympiad - circumcenter */<br /> I=incenter(A,B,C); /* olympiad - incenter */<br /> draw(A--B--C--cycle);<br /> dot(O);<br /> dot(I);<br /> draw(circumcircle(A,B,C)); /* olympiad - circumcircle */<br /> draw(incircle(A,B,C)); /* olympiad - incircle */<br /> label(&quot;$I$&quot;,I,W);<br /> label(&quot;$O\$&quot;,O,S);<br /> &lt;/asy&gt;<br /> <br /> ----<br /> <br /> '''Example 8:'''<br /> import three;<br /> unitsize(1cm);<br /> size(50);<br /> currentprojection=orthographic(1/2,-1,1/2); // three - currentprojection, orthographic<br /> draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle3,red); //three - cycle3<br /> draw((0,0,0)--(0,0,1));<br /> draw((0,1,0)--(0,1,1));<br /> draw((1,1,0)--(1,1,1));<br /> draw((1,0,0)--(1,0,1));<br /> draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle3,green);<br /> <br /> '''Output 8:'''<br /> &lt;asy&gt; import three;<br /> unitsize(1cm);<br /> size(50);<br /> currentprojection=orthographic(1/2,-1,1/2); /* three - currentprojection, orthographic */<br /> draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle3,red); /*three - cycle3 */<br /> draw((0,0,0)--(0,0,1));<br /> draw((0,1,0)--(0,1,1));<br /> draw((1,1,0)--(1,1,1));<br /> draw((1,0,0)--(1,0,1));<br /> draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle3,green);&lt;/asy&gt;<br /> <br /> == See Also ==<br /> [http://piprim.tuxfamily.org/asymptote/ Many more Asymptote examples]<br /> <br /> [[Asymptote: Macros and Packages|Next: Macros and Packages]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Macros_and_Packages&diff=24108 Asymptote: Macros and Packages 2008-03-17T21:38:35Z <p>Fedja: /* The Olympiad Package */</p> <hr /> <div>{{Asymptote}}<br /> <br /> ==Definitions==<br /> You can define your own functions in Asymptote. As an example, let's say you wanted to make a function called &lt;tt&gt;newfunction&lt;/tt&gt; that takes a pair &lt;math&gt;(a,b)&lt;/math&gt; and a real value &lt;math&gt;r&lt;/math&gt; as input, and returns the pair &lt;math&gt;(a+r,b+r)&lt;/math&gt;. In addition, you want it to simply return the pair &lt;math&gt;(a,b)&lt;/math&gt; if no value of &lt;math&gt;r&lt;/math&gt; is specified, so you want &lt;math&gt;r&lt;/math&gt; to default to &lt;math&gt;0&lt;/math&gt;. The code would be as follows:<br /> pair newfunction(pair z, real r=0)<br /> {<br /> real a,b;<br /> a=z.x;<br /> b=z.y;<br /> return (a+r,b+r);<br /> }<br /> <br /> Put this definition in an asymptote document and then test it using some command like <br /> draw(newfunction((20,30))--newfunction((20,30),30)--(0,0)--cycle); <br /> See if it works!<br /> <br /> Notice that the function must be declared a pair since it returns a pair, and each of the variables must be declared some data type too. The default value of &lt;math&gt;r&lt;/math&gt; was set to &lt;math&gt;0&lt;/math&gt; by &lt;math&gt;r=0&lt;/math&gt;, and the actual function procedure goes in between &lt;tt&gt;{}&lt;/tt&gt;. This is the general format for a function definition.<br /> <br /> ==Packages==<br /> Asymptote comes with several packages that contain useful functions for various purposes. For example, the package &lt;tt&gt;graph.asy&lt;/tt&gt; contains the function <br /> Circle(pair p, real r, int n=400);<br /> which is a more accurate circle (having 400 nodes by default) than the built-in &lt;tt&gt;circle&lt;/tt&gt; command. To use this function and others in graph.asy, simply put the command<br /> import graph;<br /> at the top of your Asymptote document.<br /> <br /> You can create your own package by simply creating a new .asy file (say &lt;tt&gt;MyMacros.asy&lt;/tt&gt;) with your own definitions in it, and saving it in the directory in which Asymptote is installed (&lt;tt&gt;C:\Program Files\Asymptote&lt;/tt&gt; by default). Then &lt;tt&gt;import MyMacros;&lt;/tt&gt; in your document, and you'll be set!<br /> <br /> ===The Olympiad Package===<br /> We have created an Olympiad package for Asymptote which includes macros for all the constructions that come up most often in Olympiad geometry problems! You can obtain the package olympiad.asy by clicking [[http://web.mit.edu/monks/www/olympiad.asy here]], (the newer version with fewer bugs is available [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=165767 here]) and saving the page/file as &quot;olympiad.asy&quot; in your Asymptote directory (&lt;tt&gt;C:\Program Files\Asymptote&lt;/tt&gt; by default). <br /> <br /> This package includes the following definitions:<br /> <br /> [[Image:Olympiad1.gif]]<br /> <br /> [[Image:Olympiad2.gif]]<br /> <br /> [[Image:Olympiad3.gif]]<br /> <br /> [[Image:Olympiad4.gif]]<br /> <br /> [[Image:Olympiad5.gif]]<br /> <br /> '''Note:''' A sequence of variables without type declarations indicates that they are the same type as the variable preceding it. For example, the notation &lt;tt&gt;concurrent(pair A, B, C, D, E, F)&lt;/tt&gt; indicates that all of the variables should have type pair.<br /> <br /> &lt;tt&gt;*&lt;/tt&gt; These boolean functions test for equality within &lt;math&gt;10^{-5}&lt;/math&gt; ps points in order to avoid approximation errors.<br /> <br /> [[Asymptote: Advanced|Next: Advanced]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Analysis&diff=22918 Analysis 2008-02-02T23:41:49Z <p>Fedja: </p> <hr /> <div>'''Analysis''' is the part of mathematics that primarily deals with properties of [[function]]s. While there is no way to define exactly what is &quot;analysis&quot; and what is not, one can be pretty sure that something has an analytical flavor every time he hears such words as [[limit]], [[integral]], [[derivative]], [[series]], etc.<br /> <br /> The foundations of mathematical analysis as we know it today were laid in 17-20th centuries starting with the development of integral and differential calculus by Newton and Leibnitz and ending with the Lebesgue theory of measure and integration and functional analysis.<br /> <br /> <br /> {{stub}}<br /> <br /> [[Category:Calculus]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Euclid%27s_proof_of_the_infinitude_of_primes&diff=22328 Talk:Euclid's proof of the infinitude of primes 2008-01-11T23:53:39Z <p>Fedja: New page: Erm... Shouldn't it be &quot;infi&lt;b&gt;NI&lt;/b&gt;tude&quot;? ~~~~</p> <hr /> <div>Erm... Shouldn't it be &quot;infi&lt;b&gt;NI&lt;/b&gt;tude&quot;? [[User:Fedja|Fedja]] 18:53, 11 January 2008 (EST)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Basics&diff=15800 Asymptote: Basics 2007-08-28T13:51:10Z <p>Fedja: /* Size and Unitsize */</p> <hr /> <div>{{Asymptote}}<br /> <br /> == Syntax ==<br /> In Asymptote, every command should be followed by a semicolon (;). This tells Asymptote how to separate one command from the next. For example, the command &lt;tt&gt;draw(A--B)&lt;/tt&gt; draws a line segment from point &lt;math&gt;A&lt;/math&gt; to &lt;math&gt;B&lt;/math&gt; given as coordinate pairs. Thus, if you wanted to draw two line segments, say one of them from (0,0) to (50,50) (in units of PostScript points - see below for the explanation of units and size) and the other from (50,0) to (0,50), you can create the following document:<br /> draw((0,0)--(50,50));<br /> draw((0,50)--(50,0));<br /> <br /> The two commands do not need to be on separate lines; it is the semicolon that separates them. However, putting the commands on separate lines does not change the output, so it is often useful to separate your commands in this way in order to organize your code. Whitespaces before and after commands are also not read by Asymptote, so any line can be indented as far as desired for clarity's sake.<br /> <br /> To write comments in your code that do not affect the output at all, simply start a line with two forward slashes: &lt;tt&gt;//&lt;/tt&gt; as in<br /> // The following line is drawn from (0,0) to (50,50)<br /> draw((0,0)--(50,50));<br /> <br /> ==Variables and Data Types==<br /> Asymptote parses your code into substrings which have a certain '''data type''', for example a ''real'' (like &lt;math&gt;1.5&lt;/math&gt;) or a ''pair'' (like &lt;math&gt;(2,3)&lt;/math&gt;). Each new variable that you declare must be declared as a data type that Asymptote recognizes, by the command &lt;tt&gt;[datatype] [variable];&lt;/tt&gt;. For example, if you wanted to declare the variable &lt;math&gt;n&lt;/math&gt; to have type integer, you can use the command<br /> int n;<br /> <br /> After it is declared, you can store a specific value in a variable using the &lt;math&gt;=&lt;/math&gt; symbol, as in<br /> n=3;<br /> <br /> These two commands can be abbreviated by the single command &lt;tt&gt;int n=3;&lt;/tt&gt;, and several integers can also be declared at once (&lt;tt&gt;int m,n,d;&lt;/tt&gt;) or even many declarations and assignations at once: &lt;tt&gt;int a,b=2,c,d=5;&lt;/tt&gt;.<br /> <br /> As another example of variable declaration, consider the picture of the X from the Syntax section above. The same picture can be made as follows:<br /> pair A,B,C,D;<br /> A=(0,0);<br /> B=(50,50);<br /> C=(0,50);<br /> D=(50,0);<br /> draw(A--B);<br /> draw(C--D);<br /> In this particular example, variable declarations made the code longer, but as you will see, declaring variables will significantly clean up your code in messier diagrams.<br /> <br /> The most commonly used data types in Asymptote are given in the following table:<br /> [[Image:Table1.gif]]<br /> <br /> ==Size and Unitsize==<br /> Asymptote is a primarily coordinate-based graphics language. Each point is a pair &lt;math&gt;(a,b)&lt;/math&gt; where &lt;math&gt;a&lt;/math&gt; is the &lt;math&gt;x&lt;/math&gt;-coordinate and &lt;math&gt;b&lt;/math&gt; is the &lt;math&gt;y&lt;/math&gt;-coordinate.<br /> <br /> However, there are many ways to choose a Cartesian coordinate system for the plane; one must pick the placement of origin and the scale on each of the &lt;math&gt;x&lt;/math&gt;- and &lt;math&gt;y&lt;/math&gt;-axes. Asymptote will place your image in the center of your output page after it is drawn, so placement of origin is actually irrelevant. By default, the unit length in both the &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; directions is the PostScript bigpoint, which has length &lt;math&gt;1/72&lt;/math&gt; inches. Thus, if you do not change the scaling on the picture, the points &lt;math&gt;(0,0)&lt;/math&gt; and &lt;math&gt;(72,0)&lt;/math&gt; are exactly one inch apart when drawn in Asymptote. However, drawing in bigpoints is inconvenient if you wish to draw a figure that is exactly 3cm wide.<br /> <br /> The function &lt;tt&gt;unitsize&lt;/tt&gt; can be used to specify the unit length for your picture. This function takes up to 3 arguments: the picture you want to scale the axes for (if this isn't specified, it defaults to &lt;tt&gt;currentpicture&lt;/tt&gt;, the picture you are drawing on), the unit length in the x direction, and the unit length in the y direction. If only one real argument is given, both the x and y unit sizes are set to this number. Thus the command<br /> unitsize(72);<br /> will tell Asymptote that from now on, your unit length is &lt;math&gt;1&lt;/math&gt; inch. Be careful when you are redefining your unit length - now that unitsize is set to &lt;math&gt;72&lt;/math&gt;, the points &lt;math&gt;(0,0)&lt;/math&gt; and &lt;math&gt;(72,0)&lt;/math&gt; are actually &lt;math&gt;72&lt;/math&gt; inches apart!<br /> <br /> Asymptote has the built-in constants &lt;tt&gt;pt&lt;/tt&gt; (1/72.27 inches), &lt;tt&gt;inch&lt;/tt&gt;, &lt;tt&gt;cm&lt;/tt&gt;, and &lt;tt&gt;mm&lt;/tt&gt; for convenience when defining lengths, so the above command can also be stated<br /> unitsize(1inch);<br /> <br /> The other useful function is &lt;tt&gt;size&lt;/tt&gt;, which specifies the exact width and height of the box that your picture (if unspecified as a first argument, this will again default to &lt;tt&gt;currentpicture&lt;/tt&gt;) will be fit into. If only one number is given, both the width and the height will be set to this number. For example, the command<br /> size(5cm,5cm);<br /> or just<br /> size(5cm);<br /> will fit the diagram to a 5cm x 5cm box regardless of the specified unitsizes.<br /> <br /> As an example, make an Asymptote document containing the following two lines:<br /> unitsize(2inch); <br /> draw(unitsquare);<br /> and see what happens as you change the &lt;math&gt;2&lt;/math&gt; inch size to several other values.<br /> <br /> <br /> [[Asymptote: Reference | Next: Reference]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Prime_Number_Theorem&diff=5981 Prime Number Theorem 2006-07-05T00:38:23Z <p>Fedja: /* Connection with Riemann zeta function */</p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> The aim of this article is to present the proof of the '''prime number theorem''' that says that the number &lt;math&gt;\pi(n)&lt;/math&gt; of [[prime]]s not exceeding &lt;math&gt;n&lt;/math&gt; is approximately &lt;math&gt;\frac n{\ln n}&lt;/math&gt; or, more precisely, that<br /> <br /> &lt;math&gt;\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.&lt;/math&gt;<br /> <br /> Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material. <br /> <br /> We shall start with some elementary observations due to Chebyshev. <br /> ==Chebyshev's estimates==<br /> The key observation is that &lt;math&gt;{2m\choose m}=\frac{(2m)!}{(m!)^2}&lt;/math&gt; is divisible by all primes &lt;math&gt;p&lt;/math&gt; satisfying &lt;math&gt;m&lt;p\le 2m&lt;/math&gt;. Indeed, every such prime appears in the numerator &lt;math&gt;(2m)!&lt;/math&gt; and does not appear in the denominator &lt;math&gt;(m!)^2&lt;/math&gt;. Thus, &lt;math&gt;\prod_{m&lt;p\le 2m}p\le {2m\choose m}\le 2^{2m}&lt;/math&gt; (from now on, &lt;math&gt;p&lt;/math&gt; will always stand for a prime number, so, to shorten the notation, we will not explicitly write &quot;&lt;math&gt;p&lt;/math&gt; is prime&quot; in the descriptions of sum and product ranges). Similarly, considering &lt;math&gt;{2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}&lt;/math&gt;, we see that <br /> &lt;math&gt;\prod_{m+1&lt;p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}&lt;/math&gt; (the last inequality holds because &lt;math&gt;{2m+1\choose m}={2m+1\choose m+1}&lt;/math&gt; and &lt;math&gt;{2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}&lt;/math&gt;). Now we are ready to prove the <br /> ===Upper bound for the product of primes===<br /> ====Lemma 1====<br /> For every positive integer &lt;math&gt;n&lt;/math&gt;, we have<br /> &lt;math&gt;\prod_{p\le n}p\le 4^n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 1====<br /> [[Induction]] on &lt;math&gt;n&lt;/math&gt;. The base &lt;math&gt;n=1&lt;/math&gt; is obvious. Suppose now that the statement holds for all numbers strictly less than &lt;math&gt;n&lt;/math&gt;. If &lt;math&gt;n=2m&lt;/math&gt; is even, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m}p\right)\cdot \left(\prod_{m&lt;p\le 2m}p\right)\le<br /> 4^m 2^{2m}=4^{2m}=4^n.<br /> &lt;/math&gt;<br /> <br /> If &lt;math&gt;n=2m+1&lt;/math&gt; is odd, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m+1}p\right)\cdot \left(\prod_{m+1&lt;p\le 2m+1}p\right)\le<br /> 4^{m+1} 2^{2m}=4^{2m+1}=4^n.<br /> &lt;/math&gt;<br /> ----<br /> From this lemma we can easily derive the <br /> ===Upper bound for the number of primes===<br /> ====Lemma 2====<br /> &lt;math&gt;\pi(n)\le 4\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 1 as &lt;math&gt;\sum_{p\le n}\ln p\le n\ln 4&lt;/math&gt;. It follows that<br /> &lt;math&gt;\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n&lt;p&lt;n}\ln p\le n\ln 4&lt;/math&gt;.<br /> But then &lt;math&gt;\pi(n)\le 2\ln 4\frac{n}{\ln n}+\pi(\sqrt n)\le 2\ln 4\,\frac{n}{\ln n}+\sqrt n&lt; 4\frac{n}{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. <br /> ===Lower bound for the product of primes===<br /> ====Lemma 3====<br /> &lt;math&gt;\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}&lt;/math&gt;.<br /> <br /> ====Proof of Lemma 3====<br /> The idea is again to investigate the [[prime factorization]] of <br /> &lt;math&gt;{n\choose \lfloor \frac n2 \rfloor}&lt;/math&gt;. We shall give the proof for odd &lt;math&gt;n=2m+1&lt;/math&gt; (the case of even &lt;math&gt;n&lt;/math&gt; is similar). Recall that the power in which a prime number &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;\ell!&lt;/math&gt; equals &lt;math&gt;\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots&lt;/math&gt; (see [[factorial]] for the proof).<br /> Therefore, the power in which &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;{n\choose m}&lt;/math&gt; equals &lt;math&gt;\sum_{k\ge 1}\left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac m{p^k}\right\rfloor-\left\lfloor \frac {m+1}{p^k}\right\rfloor\right)&lt;/math&gt; Note that each term in the last sum does not exceed &lt;math&gt;1&lt;/math&gt; and the number of non-zero terms does not exceed &lt;math&gt;\left\lfloor {\log_p n}\right\rfloor&lt;/math&gt;, which is &lt;math&gt;1&lt;/math&gt; for all &lt;math&gt;\sqrt n&lt;p\le n&lt;/math&gt;.<br /> Hence <br /> <br /> &lt;math&gt;{n\choose m}\le \left(\prod_{\sqrt n&lt;p\le n}p\right)\cdot\left(\prod_{p\le \sqrt n}p^{\lfloor\log_p n\rfloor}\right)\le \left(\prod_{p\le n}p\right)\cdot n^{\pi(\sqrt n)}\le n^{\sqrt n}\cdot \prod_{p\le n}p&lt;/math&gt;.<br /> <br /> On the other hand, &lt;math&gt;{n\choose m}&lt;/math&gt; is the largest of the &lt;math&gt;n+1&lt;/math&gt; binomial coefficients whose sum is &lt;math&gt;2^n&lt;/math&gt;. Thus, &lt;math&gt;{n\choose m}\ge \frac{2^n}{(n+1)}&lt;/math&gt; whence the estimate of the lemma.<br /> ===Lower bound for the number of primes===<br /> ====Lemma 4====<br /> &lt;math&gt;\pi(n)\ge \frac 12\,\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 3 as &lt;math&gt;\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n &gt; \frac 12 n&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;. <br /> But the left hand side does not exceed &lt;math&gt;\pi(n)\ln n&lt;/math&gt; whence the lemma.<br /> <br /> ----<br /> We haven't proved the prime number theorem yet, but we showed that <br /> &lt;math&gt;\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}&lt;/math&gt;<br /> for all sufficiently large &lt;math&gt;n&lt;/math&gt;. For many readers it is probably a good idea to stop here and to proceed to [[Bertrand's postulate]]. The material below this point requires good knowledge of analysis and is, probably, accessible to college students only.<br /> <br /> ==Von Mangoldt function and reformulation of the prime number theorem==<br /> <br /> For a positive integer &lt;math&gt;n&lt;/math&gt;, define &lt;math&gt;\Lambda(n)=\ln p&lt;/math&gt; if &lt;math&gt;n&lt;/math&gt; is a pure positive integer power of a prime &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;\Lambda(n)=0&lt;/math&gt; otherwise (so &lt;math&gt;\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2&lt;/math&gt;, &lt;math&gt;\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3&lt;/math&gt; and so on. Let &lt;math&gt;\psi(x)=\sum_{n\le x}\Lambda(n)&lt;/math&gt; <br /> ====Lemma 5====<br /> The prime number theorem is equivalent to &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> ====Proof of Lemma 5====<br /> Note that for &lt;math&gt;x\ge 1&lt;/math&gt;, we have &lt;math&gt;\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p&lt;/math&gt;. Since &lt;math&gt;\lfloor \log_p x\rfloor\ln p\le \ln x&lt;/math&gt;, we immediately get &lt;math&gt;\psi(x)\le \pi(x)\ln x&lt;/math&gt;. Let now &lt;math&gt;\alpha&lt;1&lt;/math&gt;. For &lt;math&gt;x^\alpha&lt;p\le x&lt;/math&gt;, we have &lt;math&gt;\ln p\ge \alpha \ln x&lt;/math&gt; and, therefore, &lt;math&gt;\psi(x)\ge \sum_{x^\alpha&lt;p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x&lt;/math&gt;, which can be rewritten as &lt;math&gt;\pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> \pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;.&lt;/math&gt; <br /> <br /> Assume now that we know that &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> Dividing by &lt;math&gt;x&lt;/math&gt; and passing to the limit as &lt;math&gt;x\to+\infty&lt;/math&gt;, we get<br /> <br /> &lt;math&gt;1\le\liminf_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le \limsup_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le\frac 1\alpha\,.&lt;/math&gt;<br /> <br /> Since it is true for all &lt;math&gt;\alpha&lt;1&lt;/math&gt;, we conclude that<br /> &lt;math&gt;\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1&lt;/math&gt;. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise.<br /> <br /> ==Connection with Riemann [[zeta function]]==<br /> Write &lt;math&gt;\zeta&lt;/math&gt;-function as the Euler product &lt;math&gt;\zeta(s)=\prod_p (1-p^{-s})^{-1}&lt;/math&gt; and take minus logarithmic derivative of both sides. We'll get the formula<br /> <br /> &lt;math&gt;-\frac{\zeta'(s)}{\zeta(s)}=\sum_p\frac {p^{-s}\ln p}{1-p^{-s}}=\sum_p\sum_{k\ge 1}\frac{\ln p}{p^{ks}}=\sum_{n\ge 1}\frac {\Lambda(n)}{n^s}=\int_1^\infty \frac{d\psi(x)}{x^s}<br /> =s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}&lt;/math&gt;<br /> <br /> if &lt;math&gt;\Re s&gt;1&lt;/math&gt;<br /> <br /> Let now &lt;math&gt;\xi(t)=\frac{\psi(e^t)}{e^t}-1&lt;/math&gt;. Then, making the change of variable &lt;math&gt;x=e^t&lt;/math&gt; in the last integral, we get<br /> <br /> &lt;math&gt;\int_{0}^\infty \xi(t)e^{-(s-1)t}\,dt=-\frac{\zeta'(s)}{s\zeta(s)}-\frac 1{s-1}&lt;/math&gt; <br /> for all &lt;math&gt;s&lt;/math&gt; with &lt;math&gt;\Re s&gt;1&lt;/math&gt;.<br /> <br /> Since the &lt;math&gt;\zeta&lt;/math&gt;-function has a simple pole at &lt;math&gt;s=1&lt;/math&gt; and no zeroes on the line &lt;math&gt;\Re s=1&lt;/math&gt;, the right hand side represents a function [[analytic]] in some domain containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 1\}&lt;/math&gt;<br /> <br /> ==End of proof==<br /> <br /> By the Chebyshev's estimates, we have &lt;math&gt;-1\le\xi(t)\le 3&lt;/math&gt; for large &lt;math&gt;t&lt;/math&gt;, so &lt;math&gt;\xi(t)&lt;/math&gt; is bounded and we can apply [[Newman's Tauberian Theorem]] and conclude that &lt;math&gt;\int_0^\infty \xi(t)\,dt&lt;/math&gt; converges. <br /> <br /> Now note that &lt;math&gt;\xi(t)&lt;/math&gt; cannot decrease fast. More precisely, <br /> <br /> &lt;math&gt;\xi(t')-\xi(t)<br /> =\frac{\psi(e^{t'})}{e^{t'}}-\frac{\psi(e^{t})}{e^{t}}\ge<br /> \frac{\psi(e^{t})}{e^{t'}}-\frac{\psi(e^{t})}{e^{t}}<br /> =\frac{\psi(e^{t})}{e^{t}}(e^{t-t'}-1)\ge <br /> -\frac{\psi(e^{t})}{e^{t}}(t'-t)\ge <br /> -C(t'-t)&lt;/math&gt; <br /> <br /> for all &lt;math&gt;t'&gt;t&lt;/math&gt; with some absolute constant &lt;math&gt;C&lt;+\infty&lt;/math&gt;. The last step is to show that, together with convergence of the integral &lt;math&gt;\int_0^\infty \xi(t)\,dt&lt;/math&gt;, this condition implies that &lt;math&gt;\xi(t)\to 0&lt;/math&gt; as &lt;math&gt;\displaystyle t\to +\infty&lt;/math&gt;. <br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Set&diff=5954 Set 2006-07-04T20:04:13Z <p>Fedja: /* Subsets */</p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> <br /> The notion of a set is one of the fundamental notions in mathematics that has to be left undefined. Of course, we have plenty of synonyms for the word set like ''collection, ensemble, group'', etc. but those names really do not define the meaning of the word ''set'': all they can do is to replace it in various sentences. So, instead of defining what sets are, one has to define what can be done with them or, in other words, what axioms the sets satisfy. These axioms are chosen to agree with our intuitive concept of a set on one hand and to allow various, sometimes quite sophisticated, mathematical constructions on the other hand. For the full collection of these axioms, see [[Zermelo-Fraenkel Axioms]]. In this article we shall present just a brief discussion of the most common properties of sets and operations related to them.<br /> <br /> ==Relation of ''belonging''==<br /> <br /> The most important property of sets is that, for every ''object'' &lt;math&gt;x&lt;/math&gt; and a set &lt;math&gt;S&lt;/math&gt;, we can say whether &lt;math&gt;x&lt;/math&gt; belongs to &lt;math&gt;S&lt;/math&gt; (written as &lt;math&gt;x\in S&lt;/math&gt;) or not (written as &lt;math&gt;x\notin S&lt;/math&gt;). Two sets &lt;math&gt;S'&lt;/math&gt; and &lt;math&gt;S''&lt;/math&gt; are equal if they include the same objects, i.e., if for every object &lt;math&gt;x&lt;/math&gt;, we have &lt;math&gt;x\in S'&lt;/math&gt; if and only if &lt;math&gt;x\in S''&lt;/math&gt;. <br /> <br /> ==Specifying a set by listing its objects==<br /> <br /> It means that in order to determine the set, it suffices to tell which objects belong to this set. If you have just several such objects, all you need to do is to list them. So, you can specify the set consisting of the numbers &lt;math&gt;1,3,5&lt;/math&gt;, and &lt;math&gt;239&lt;/math&gt;, for example. (The standard notation for this set is &lt;math&gt;\{1,3,5,239\}&lt;/math&gt;. note that the order in which the terms are listed is completely unimportant: we have to follow some order when writing things in one line but you should actually imagine those numbers flowing freely inside those curly braces with no preference given to any of them. What matters is that these four numbers are in the set and everything else is out).<br /> But how do you specify sets that have very many (maybe [[infinite]]ly many) elements? You cannon list them all even if you spend your entire life writing! <br /> <br /> ==Specifying a set by the common property of its elements==<br /> <br /> Another way to specify a set is to use some property to tell when an object belongs to this set. For instance, we may try to think (alas, only try!) of the set of all objects with green hair. In this case we do not even try to list all such objects. We just decide that something belongs to this set if it has green hair and doesn't belong to it otherwise. This is a wonderful way to describe a set. Unfortunately, it just doesn't work that simply. Indeed, consider the property that an object is a set that does not belong to itself (remember, that, given a set, we should be able to tell about '''every''' object whether it belongs to this set or not; in particular, we can ask this question about the set itself). It is easy to see that the set &lt;math&gt;S&lt;/math&gt; specified by this property can neither belong, nor not belong to itself and our whole theory gets self-contradictory. So, this way to describe sets should be used with extreme caution. The way out is that such a description is allowed only in much weaker form: given a set &lt;math&gt;S&lt;/math&gt; and a property &lt;math&gt;P&lt;/math&gt;, we can define a new set &lt;math&gt;S'&lt;/math&gt; of objects in the set &lt;math&gt;S&lt;/math&gt; that satisfy the property &lt;math&gt;P&lt;/math&gt;.<br /> <br /> ==Subsets==<br /> We say that a set &lt;math&gt;A&lt;/math&gt; is a subset of a set &lt;math&gt;S&lt;/math&gt; if every object &lt;math&gt;x&lt;/math&gt; that belongs to &lt;math&gt;A&lt;/math&gt; also belongs to &lt;math&gt;S&lt;/math&gt;. For example, the sets &lt;math&gt;\{1,2\}&lt;/math&gt; and &lt;math&gt;\{2,3\}&lt;/math&gt; are subsets of the set &lt;math&gt;\{1,2,3\}&lt;/math&gt; but the set &lt;math&gt;\{1,6\}&lt;/math&gt; is not.<br /> <br /> ==Power set==<br /> <br /> ==Union and intersection==<br /> <br /> ==Empty set==<br /> <br /> ==Infinite sets==<br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Newman%27s_Tauberian_Theorem&diff=5945 Newman's Tauberian Theorem 2006-07-04T16:10:39Z <p>Fedja: finished the article; comments and improvements are welcome.</p> <hr /> <div>==Statement==<br /> Let &lt;math&gt;f:(0,+\infty)\to\mathbb C&lt;/math&gt; be a bounded function. Assume that its [[Laplace transform]] &lt;math&gt;F(s)=\int_0^\infty f(t)e^{-st}\,dt&lt;/math&gt; (which is well-defined by this formula for &lt;math&gt;\Re s&gt;0&lt;/math&gt;) admits an analytic extension (which we'll denote by the same letter &lt;math&gt;F&lt;/math&gt;) to some open domain &lt;math&gt;E&lt;/math&gt; containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 0\}&lt;/math&gt;. Then the integral &lt;math&gt;\int_0^\infty f(t)\,dt&lt;/math&gt; converges and its value equals &lt;math&gt;F(0)&lt;/math&gt;.<br /> <br /> ==Proof==<br /> For every &lt;math&gt;T&gt;0&lt;/math&gt;, let &lt;math&gt;F_T(s)=\int_0^T f(t)e^{-st}\,dt&lt;/math&gt;. The function &lt;math&gt;F_T&lt;/math&gt; is defined and analytic on the entire complex plane &lt;math&gt;\mathbb C&lt;/math&gt;. The conclusion of the theorem is equivalent to the assertion &lt;math&gt;\lim_{T\to+\infty} F_T(0)=F(0)&lt;/math&gt;. Now, choose some big &lt;math&gt;R&gt;0&lt;/math&gt; and consider the contour &lt;math&gt;\Gamma=\Gamma_+\cup\Gamma_-&lt;/math&gt; as on the picture below.<br /> <br /> [[Image:Newmans_Tauberian_Contour.PNG|Contour picture]]<br /> <br /> Here &lt;math&gt;\Gamma_+&lt;/math&gt; is a semicircle and &lt;math&gt;\Gamma_-&lt;/math&gt; is any smooth curve that lies to the left of the imaginary axis except for its endpoints and such that the domain &lt;math&gt;D&lt;/math&gt; bounded by &lt;math&gt;\Gamma&lt;/math&gt; is entirely contained in &lt;math&gt;E&lt;/math&gt;. By the [[Cauchy Integral Formula|Cauchy integral formula]], we have <br /> <br /> &lt;math&gt;F(0)-F_T(0)=\frac 1{2\pi i}\int_\Gamma K(z)(F(z)-F_T(z))\,dz&lt;/math&gt;<br /> <br /> where &lt;math&gt;K(z)&lt;/math&gt; is any kernel that is analytic in some neighbourhood of &lt;math&gt;D&lt;/math&gt; except for the point &lt;math&gt;0&lt;/math&gt; where it must have a simple [[pole]] with [[residue]] &lt;math&gt;1&lt;/math&gt;.<br /> <br /> The trick is to choose an appropriate kernel (depending on &lt;math&gt;T&lt;/math&gt;) that makes the integral easy to estimate. To make a good choice, let us first estimate the difference <br /> &lt;math&gt;F(z)-F_T(z)&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. We have <br /> <br /> &lt;math&gt;|F(z)-F_T(z)|= \left|\int_T^{+\infty}f(t)e^{-zt}\,dt\right|<br /> \le M\int_T^{+\infty}e^{-\Re z\,t}\,dt=M\frac {e^{-\Re z\,T}}{\Re z}<br /> &lt;/math&gt;<br /> <br /> where &lt;math&gt;M&lt;/math&gt; is a bound for &lt;math&gt;|f|&lt;/math&gt; on &lt;math&gt;(0,+\infty)&lt;/math&gt;.<br /> Thus, we should kill the denominator &lt;math&gt;\Re z&lt;/math&gt; if we want the integral to converge. On the other hand, we can afford the kernel &lt;math&gt;K(z)&lt;/math&gt; grow as &lt;math&gt;e^{T\Re z}&lt;/math&gt; in the right half-plane (actually, we do not need any growth of &lt;math&gt;K(z)&lt;/math&gt; in the right half-plane for its own sake, but we need some decay in the left half-plane to estimate the integral over &lt;math&gt;\Gamma_-&lt;/math&gt; and it is impossible to get the latter without the first). This leads us to the choice <br /> <br /> &lt;math&gt;K(z)=\left(\frac 1z+\frac z{R^2}\right)e^{Tz}&lt;/math&gt;<br /> <br /> Note that &lt;math&gt;K(\pm iR)=0&lt;/math&gt;, so the unpleasant denominator &lt;math&gt;\Re z&lt;/math&gt; is, indeed, killed by &lt;math&gt;K&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. Also, &lt;math&gt;K&lt;/math&gt; decays in the left half-plane as fast as only is allowed by the exponential growth restriction in the right half-plane. This is not the only possible choice that will work, of course, but it is the simplest and the most<br /> elegant one.<br /> <br /> Once this tricky choice is made, the rest is fairly straightforward.<br /> The integral over &lt;math&gt;\Gamma_+&lt;/math&gt; does not exceed &lt;math&gt;\frac {2\pi M}{R}&lt;/math&gt; (just use the standard parametrization &lt;math&gt;z=Re^{i\theta}&lt;/math&gt; and notice that &lt;math&gt;\frac 1z+\frac z{R^2}=\frac 2R\cos\theta=\frac 2{R^2}\Re z&lt;/math&gt; and that the exponent in the kernel essentially cancels the exponent in the estimate for &lt;math&gt;|F(0)-F_T(0)|&lt;/math&gt;). To estimate the integral over &lt;math&gt;\Gamma_-&lt;/math&gt;, just write &lt;math&gt;\left|\int_{\Gamma_-}K(z)(F(z)-F_T(z))\,dz\right|\le<br /> \left|\int_{\Gamma_-}K(z)F(z)\,dz\right|+<br /> \left|\int_{\Gamma_-}K(z)F_T(z)\,dz\right|=I_1+I_2 &lt;/math&gt;.<br /> <br /> To estimate &lt;math&gt;I_2&lt;/math&gt;, note that &lt;math&gt;K(z)F_T(z)&lt;/math&gt;<br /> is analytic in the left half-plane, so we may change the integration path ot the left semicircle &lt;math&gt;\tilde\Gamma_-&lt;/math&gt;. Now, on &lt;math&gt;\tilde\Gamma_-&lt;/math&gt;, we have<br /> <br /> &lt;math&gt;|F_T(z)|\le M\int_0^T e^{-\Re z\,t}\,dt= M\frac {e^{-T\,\Re z}-1}{\Re z}\le M\frac {e^{-T\,\Re z}}{\Re z}&lt;/math&gt;. <br /> <br /> This yields the estimate &lt;math&gt;I_2\le\frac{2\pi M}{R}&lt;/math&gt; in the same way as for the integral over &lt;math&gt;\Gamma_+&lt;/math&gt;. At last, note that, for fixed &lt;math&gt;R&lt;/math&gt;, the integrand in &lt;math&gt;I_1&lt;/math&gt; is uniformly bounded and tends to &lt;math&gt;0&lt;/math&gt; at every point of &lt;math&gt;\Gamma_-&lt;/math&gt; as &lt;math&gt;T\to +\infty&lt;/math&gt;. This allows to conclude (by the Lebesgue [[Dominated Convergence Theorem|dominated convergence theorem]] or in some more elementary way) that &lt;math&gt;I_1\to 0&lt;/math&gt; as &lt;math&gt;T\to\infty&lt;/math&gt;. Thus, given any &lt;math&gt;\varepsilon&gt;0&lt;/math&gt;, we can first fix &lt;math&gt;R&gt;0&lt;/math&gt;<br /> such that &lt;math&gt;\frac{4\pi M}R&lt;\frac\varepsilon 2&lt;/math&gt; and then choose &lt;math&gt;T_0&gt;0&lt;/math&gt; such that &lt;math&gt;I_1\le\frac\varepsilon 2&lt;/math&gt;<br /> for &lt;math&gt;T&gt;T_0&lt;/math&gt;. Then &lt;math&gt;|F(0)-F_T(0)|&lt;\varepsilon&lt;/math&gt; for &lt;math&gt;T&gt;T_0&lt;/math&gt; and we are done.<br /> <br /> ==See also==<br /> [[Tauberian theorems]], [[Prime Number Theorem|Prime number theorem]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Newman%27s_Tauberian_Theorem&diff=5944 Newman's Tauberian Theorem 2006-07-04T16:08:38Z <p>Fedja: /* Proof */</p> <hr /> <div>{{stub}}<br /> ==Statement==<br /> Let &lt;math&gt;f:(0,+\infty)\to\mathbb C&lt;/math&gt; be a bounded function. Assume that its [[Laplace transform]] &lt;math&gt;F(s)=\int_0^\infty f(t)e^{-st}\,dt&lt;/math&gt; (which is well-defined by this formula for &lt;math&gt;\Re s&gt;0&lt;/math&gt;) admits an analytic extension (which we'll denote by the same letter &lt;math&gt;F&lt;/math&gt;) to some open domain &lt;math&gt;E&lt;/math&gt; containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 0\}&lt;/math&gt;. Then the integral &lt;math&gt;\int_0^\infty f(t)\,dt&lt;/math&gt; converges and its value equals &lt;math&gt;F(0)&lt;/math&gt;.<br /> <br /> ==Proof==<br /> For every &lt;math&gt;T&gt;0&lt;/math&gt;, let &lt;math&gt;F_T(s)=\int_0^T f(t)e^{-st}\,dt&lt;/math&gt;. The function &lt;math&gt;F_T&lt;/math&gt; is defined and analytic on the entire complex plane &lt;math&gt;\mathbb C&lt;/math&gt;. The conclusion of the theorem is equivalent to the assertion &lt;math&gt;\lim_{T\to+\infty} F_T(0)=F(0)&lt;/math&gt;. Now, choose some big &lt;math&gt;R&gt;0&lt;/math&gt; and consider the contour &lt;math&gt;\Gamma=\Gamma_+\cup\Gamma_-&lt;/math&gt; as on the picture below.<br /> <br /> [[Image:Newmans_Tauberian_Contour.PNG|Contour picture]]<br /> <br /> Here &lt;math&gt;\Gamma_+&lt;/math&gt; is a semicircle and &lt;math&gt;\Gamma_-&lt;/math&gt; is any smooth curve that lies to the left of the imaginary axis except for its endpoints and such that the domain &lt;math&gt;D&lt;/math&gt; bounded by &lt;math&gt;\Gamma&lt;/math&gt; is entirely contained in &lt;math&gt;E&lt;/math&gt;. By the [[Cauchy Integral Formula|Cauchy integral formula]], we have <br /> <br /> &lt;math&gt;F(0)-F_T(0)=\frac 1{2\pi i}\int_\Gamma K(z)(F(z)-F_T(z))\,dz&lt;/math&gt;<br /> <br /> where &lt;math&gt;K(z)&lt;/math&gt; is any kernel that is analytic in some neighbourhood of &lt;math&gt;D&lt;/math&gt; except for the point &lt;math&gt;0&lt;/math&gt; where it must have a simple [[pole]] with [[residue]] &lt;math&gt;1&lt;/math&gt;.<br /> <br /> The trick is to choose an appropriate kernel (depending on &lt;math&gt;T&lt;/math&gt;) that makes the integral easy to estimate. To make a good choice, let us first estimate the difference <br /> &lt;math&gt;F(z)-F_T(z)&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. We have <br /> <br /> &lt;math&gt;|F(z)-F_T(z)|= \left|\int_T^{+\infty}f(t)e^{-zt}\,dt\right|<br /> \le M\int_T^{+\infty}e^{-\Re z\,t}\,dt=M\frac {e^{-\Re z\,T}}{\Re z}<br /> &lt;/math&gt;<br /> <br /> where &lt;math&gt;M&lt;/math&gt; is a bound for &lt;math&gt;|f|&lt;/math&gt; on &lt;math&gt;(0,+\infty)&lt;/math&gt;.<br /> Thus, we should kill the denominator &lt;math&gt;\Re z&lt;/math&gt; if we want the integral to converge. On the other hand, we can afford the kernel &lt;math&gt;K(z)&lt;/math&gt; grow as &lt;math&gt;e^{T\Re z}&lt;/math&gt; in the right half-plane (actually, we do not need any growth of &lt;math&gt;K(z)&lt;/math&gt; in the right half-plane for its own sake, but we need some decay in the left half-plane to estimate the integral over &lt;math&gt;\Gamma_-&lt;/math&gt; and it is impossible to get the latter without the first). This leads us to the choice <br /> <br /> &lt;math&gt;K(z)=\left(\frac 1z+\frac z{R^2}\right)e^{Tz}&lt;/math&gt;<br /> <br /> Note that &lt;math&gt;K(\pm iR)=0&lt;/math&gt;, so the unpleasant denominator &lt;math&gt;\Re z&lt;/math&gt; is, indeed, killed by &lt;math&gt;K&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. Also, &lt;math&gt;K&lt;/math&gt; decays in the left half-plane as fast as only is allowed by the exponential growth restriction in the right half-plane. This is not the only possible choice that will work, of course, but it is the simplest and the most<br /> elegant one.<br /> <br /> Once this tricky choice is made, the rest is fairly straightforward.<br /> The integral over &lt;math&gt;\Gamma_+&lt;/math&gt; does not exceed &lt;math&gt;\frac {2\pi M}{R}&lt;/math&gt; (just use the standard parametrization &lt;math&gt;z=Re^{i\theta}&lt;/math&gt; and notice that &lt;math&gt;\frac 1z+\frac z{R^2}=\frac 2R\cos\theta=\frac 2{R^2}\Re z&lt;/math&gt; and that the exponent in the kernel essentially cancels the exponent in the estimate for &lt;math&gt;|F(0)-F_T(0)|&lt;/math&gt;). To estimate the integral over &lt;math&gt;\Gamma_-&lt;/math&gt;, just write &lt;math&gt;\left|\int_{\Gamma_-}K(z)(F(z)-F_T(z))\,dz\right|\le<br /> \left|\int_{\Gamma_-}K(z)F(z)\,dz\right|+<br /> \left|\int_{\Gamma_-}K(z)F_T(z)\,dz\right|=I_1+I_2 &lt;/math&gt;.<br /> <br /> To estimate &lt;math&gt;I_2&lt;/math&gt;, note that &lt;math&gt;K(z)F_T(z)&lt;/math&gt;<br /> is analytic in the left half-plane, so we may change the integration path ot the left semicircle &lt;math&gt;\tilde\Gamma_-&lt;/math&gt;. Now, on &lt;math&gt;\tilde\Gamma_-&lt;/math&gt;, we have<br /> <br /> &lt;math&gt;|F_T(z)|\le M\int_0^T e^{-\Re z\,t}\,dt= M\frac {e^{-T\,\Re z}-1}{\Re z}\le M\frac {e^{-T\,\Re z}}{\Re z}&lt;/math&gt;. <br /> <br /> This yields the estimate &lt;math&gt;I_2\le\frac{2\pi M}{R}&lt;/math&gt; in the same way as for the integral over &lt;math&gt;\Gamma_+&lt;/math&gt;. At last, note that, for fixed &lt;math&gt;R&lt;/math&gt;, the integrand in &lt;math&gt;I_1&lt;/math&gt; is uniformly bounded and tends to &lt;math&gt;0&lt;/math&gt; at every point of &lt;math&gt;\Gamma_-&lt;/math&gt; as &lt;math&gt;T\to +\infty&lt;/math&gt;. This allows to conclude (by the Lebesgue [[Dominated Convergence Theorem|dominated convergence theorem]] or in some more elementary way) that &lt;math&gt;I_1\to 0&lt;/math&gt; as &lt;math&gt;T\to\infty&lt;/math&gt;. Thus, given any &lt;math&gt;\varepsilon&gt;0&lt;/math&gt;, we can first fix &lt;math&gt;R&gt;0&lt;/math&gt;<br /> such that &lt;math&gt;\frac{4\pi M}R&lt;\frac\varepsilon 2&lt;/math&gt; and then choose &lt;math&gt;T_0&gt;0&lt;/math&gt; such that &lt;math&gt;I_1\le\frac\varepsilon 2&lt;/math&gt;<br /> for &lt;math&gt;T&gt;T_0&lt;/math&gt;. Then &lt;math&gt;|F(0)-F_T(0)|&lt;\varepsilon&lt;/math&gt; for &lt;math&gt;T&gt;T_0&lt;/math&gt; and we are done.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Newman%27s_Tauberian_Theorem&diff=5934 Newman's Tauberian Theorem 2006-07-03T22:52:57Z <p>Fedja: /* Proof */</p> <hr /> <div>{{stub}}<br /> ==Statement==<br /> Let &lt;math&gt;f:(0,+\infty)\to\mathbb C&lt;/math&gt; be a bounded function. Assume that its [[Laplace transform]] &lt;math&gt;F(s)=\int_0^\infty f(t)e^{-st}\,dt&lt;/math&gt; (which is well-defined by this formula for &lt;math&gt;\Re s&gt;0&lt;/math&gt;) admits an analytic extension (which we'll denote by the same letter &lt;math&gt;F&lt;/math&gt;) to some open domain &lt;math&gt;E&lt;/math&gt; containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 0\}&lt;/math&gt;. Then the integral &lt;math&gt;\int_0^\infty f(t)\,dt&lt;/math&gt; converges and its value equals &lt;math&gt;F(0)&lt;/math&gt;.<br /> <br /> ==Proof==<br /> For every &lt;math&gt;T&gt;0&lt;/math&gt;, let &lt;math&gt;F_T(s)=\int_0^T f(t)e^{-st}\,dt&lt;/math&gt;. The function &lt;math&gt;F_T&lt;/math&gt; is defined and analytic on the entire complex plane &lt;math&gt;\mathbb C&lt;/math&gt;. The conclusion of the theorem is equivalent to the assertion &lt;math&gt;\lim_{T\to+\infty} F_T(0)=F(0)&lt;/math&gt;. Now, choose some big &lt;math&gt;R&gt;0&lt;/math&gt; and consider the contour &lt;math&gt;\Gamma=\Gamma_+\cup\Gamma_-&lt;/math&gt; as on the picture below.<br /> <br /> [[Image:Newmans_Tauberian_Contour.PNG|Contour picture]]<br /> <br /> Here &lt;math&gt;\Gamma_+&lt;/math&gt; is a semicircle and &lt;math&gt;\Gamma_-&lt;/math&gt; is any smooth curve that lies to the left of the imaginary axis except for its endpoints and such that the domain &lt;math&gt;D&lt;/math&gt; bounded by &lt;math&gt;\Gamma&lt;/math&gt; is entirely contained in &lt;math&gt;E&lt;/math&gt;. By the [[Cauchy Integral Formula|Cauchy integral formula]], we have <br /> <br /> &lt;math&gt;F(0)-F_T(0)=\frac 1{2\pi i}\int_\Gamma K(z)(F(z)-F_T(z))\,dz&lt;/math&gt;<br /> <br /> where &lt;math&gt;K(z)&lt;/math&gt; is any kernel that is analytic in some neighbourhood of &lt;math&gt;D&lt;/math&gt; except for the point &lt;math&gt;0&lt;/math&gt; where it must have a simple [[pole]] with [[residue]] &lt;math&gt;1&lt;/math&gt;.<br /> <br /> The trick is to choose an appropriate kernel (depending on &lt;math&gt;T&lt;/math&gt;) that makes the integral easy to estimate. To make a good choice, let us first estimate the difference <br /> &lt;math&gt;F(z)-F_T(z)&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. We have <br /> <br /> &lt;math&gt;|F(z)-F_T(z)|= \left|\int_T^{+\infty}f(t)e^{-zt}\,dt\right|<br /> \le M\int_T^{+\infty}e^{-\Re z\,t}\,dt=M\frac {e^{-\Re z\,T}}{\Re z}<br /> &lt;/math&gt;<br /> <br /> where &lt;math&gt;M&lt;/math&gt; is a bound for &lt;math&gt;|f|&lt;/math&gt; on &lt;math&gt;(0,+\infty)&lt;/math&gt;.<br /> Thus, we should kill the denominator &lt;math&gt;\Re z&lt;/math&gt; if we want the integral to converge. On the other hand, we can afford the kernel &lt;math&gt;K(z)&lt;/math&gt; grow as &lt;math&gt;e^{T\Re z}&lt;/math&gt; in the right half-plane (actually, we do not need any growth of &lt;math&gt;K(z)&lt;/math&gt; in the right half-plane for its own sake, but we need some decay in the left half-plane to estimate the integral over &lt;math&gt;\Gamma_-&lt;/math&gt; and it is impossible to get the latter without the first). This leads us to the choice <br /> <br /> &lt;math&gt;K(z)=\left(\frac 1z+\frac z{R^2}\right)e^{Tz}&lt;/math&gt;<br /> <br /> Note that &lt;math&gt;K(\pm iR)=0&lt;/math&gt;, so the unpleasant denominator &lt;math&gt;\Re z&lt;/math&gt; is, indeed, killed by &lt;math&gt;K&lt;/math&gt; on &lt;math&gt;\Gamma_+&lt;/math&gt;. Also, &lt;math&gt;K&lt;/math&gt; decays in the left half-plane as fast as only is allowed by the exponential growth restriction in the right half-plane. This is not the only possible choice that will work, of course, but it is the simplest and the most<br /> elegant one.<br /> <br /> Once this tricky choice is made, the rest is fairly straightforward.<br /> The integral over &lt;math&gt;\Gamma_+&lt;/math&gt; does not exceed<br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Newman%27s_Tauberian_Theorem&diff=5933 Newman's Tauberian Theorem 2006-07-03T22:05:55Z <p>Fedja: </p> <hr /> <div>{{stub}}<br /> ==Statement==<br /> Let &lt;math&gt;f:(0,+\infty)\to\mathbb C&lt;/math&gt; be a bounded function. Assume that its [[Laplace transform]] &lt;math&gt;F(s)=\int_0^\infty f(t)e^{-st}\,dt&lt;/math&gt; (which is well-defined by this formula for &lt;math&gt;\Re s&gt;0&lt;/math&gt;) admits an analytic extension (which we'll denote by the same letter &lt;math&gt;F&lt;/math&gt;) to some open domain &lt;math&gt;E&lt;/math&gt; containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 0\}&lt;/math&gt;. Then the integral &lt;math&gt;\int_0^\infty f(t)\,dt&lt;/math&gt; converges and its value equals &lt;math&gt;F(0)&lt;/math&gt;.<br /> <br /> ==Proof==<br /> <br /> [[Image:Newmans_Tauberian_Contour.PNG|Contour picture]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=File:Newmans_Tauberian_Contour.PNG&diff=5932 File:Newmans Tauberian Contour.PNG 2006-07-03T21:54:13Z <p>Fedja: </p> <hr /> <div></div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Chebyshevs_inequality&diff=5926 Talk:Chebyshevs inequality 2006-07-03T20:31:55Z <p>Fedja: </p> <hr /> <div>#REDIRECT [[Talk:Chebyshev's Inequality]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Chebyshevs_inequality&diff=5925 Chebyshevs inequality 2006-07-03T20:31:06Z <p>Fedja: </p> <hr /> <div>#REDIRECT [[Chebyshev's Inequality]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=IMO&diff=5924 IMO 2006-07-03T20:30:33Z <p>Fedja: </p> <hr /> <div>#REDIRECT[[International Mathematical Olympiad]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=International_Mathematics_Olympiad&diff=5923 International Mathematics Olympiad 2006-07-03T20:29:50Z <p>Fedja: </p> <hr /> <div>#REDIRECT [[International Mathematical Olympiad]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Set&diff=5919 Set 2006-07-03T18:59:11Z <p>Fedja: </p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> <br /> The notion of a set is one of the fundamental notions in mathematics that has to be left undefined. Of course, we have plenty of synonyms for the word set like ''collection, ensemble, group'', etc. but those names really do not define the meaning of the word ''set'': all they can do is to replace it in various sentences. So, instead of defining what sets are, one has to define what can be done with them or, in other words, what axioms the sets satisfy. These axioms are chosen to agree with our intuitive concept of a set on one hand and to allow various, sometimes quite sophisticated, mathematical constructions on the other hand. For the full collection of these axioms, see [[Zermelo-Fraenkel Axioms]]. In this article we shall present just a brief discussion of the most common properties of sets and operations related to them.<br /> <br /> ==Relation of ''belonging''==<br /> <br /> The most important property of sets is that, for every ''object'' &lt;math&gt;x&lt;/math&gt; and a set &lt;math&gt;S&lt;/math&gt;, we can say whether &lt;math&gt;x&lt;/math&gt; belongs to &lt;math&gt;S&lt;/math&gt; (written as &lt;math&gt;x\in S&lt;/math&gt;) or not (written as &lt;math&gt;x\notin S&lt;/math&gt;). Two sets &lt;math&gt;S'&lt;/math&gt; and &lt;math&gt;S''&lt;/math&gt; are equal if they include the same objects, i.e., if for every object &lt;math&gt;x&lt;/math&gt;, we have &lt;math&gt;x\in S'&lt;/math&gt; if and only if &lt;math&gt;x\in S''&lt;/math&gt;. <br /> <br /> ==Specifying a set by listing its objects==<br /> <br /> It means that in order to determine the set, it suffices to tell which objects belong to this set. If you have just several such objects, all you need to do is to list them. So, you can specify the set consisting of the numbers &lt;math&gt;1,3,5&lt;/math&gt;, and &lt;math&gt;239&lt;/math&gt;, for example. (The standard notation for this set is &lt;math&gt;\{1,3,5,239\}&lt;/math&gt;. note that the order in which the terms are listed is completely unimportant: we have to follow some order when writing things in one line but you should actually imagine those numbers flowing freely inside those curly braces with no preference given to any of them. What matters is that these four numbers are in the set and everything else is out).<br /> But how do you specify sets that have very many (maybe [[infinite]]ly many) elements? You cannon list them all even if you spend your entire life writing! <br /> <br /> ==Specifying a set by the common property of its elements==<br /> <br /> Another way to specify a set is to use some property to tell when an object belongs to this set. For instance, we may try to think (alas, only try!) of the set of all objects with green hair. In this case we do not even try to list all such objects. We just decide that something belongs to this set if it has green hair and doesn't belong to it otherwise. This is a wonderful way to describe a set. Unfortunately, it just doesn't work that simply. Indeed, consider the property that an object is a set that does not belong to itself (remember, that, given a set, we should be able to tell about '''every''' object whether it belongs to this set or not; in particular, we can ask this question about the set itself). It is easy to see that the set &lt;math&gt;S&lt;/math&gt; specified by this property can neither belong, nor not belong to itself and our whole theory gets self-contradictory. So, this way to describe sets should be used with extreme caution. The way out is that such a description is allowed only in much weaker form: given a set &lt;math&gt;S&lt;/math&gt; and a property &lt;math&gt;P&lt;/math&gt;, we can define a new set &lt;math&gt;S'&lt;/math&gt; of objects in the set &lt;math&gt;S&lt;/math&gt; that satisfy the property &lt;math&gt;P&lt;/math&gt;.<br /> <br /> ==Subsets==<br /> <br /> ==Power set==<br /> <br /> ==Union and intersection==<br /> <br /> ==Empty set==<br /> <br /> ==Infinite sets==<br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Sieve_of_Eratosthenes&diff=5891 Sieve of Eratosthenes 2006-07-03T17:31:48Z <p>Fedja: added a picture</p> <hr /> <div>===Description of the algorithm===<br /> <br /> The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with &lt;math&gt;2&lt;/math&gt; up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed, nor circled, circle it, and cross all larger numbers divisible by it. Keep doing this until all numbers are either circled or crossed. The circled numbers are the primes!<br /> <br /> <br /> Below is an example of how to use this sieve to find the primes up to<br /> &lt;math&gt;20&lt;/math&gt;. Note that after just two steps, no new crossouts appear. In general, one can forget about crossouts and start just circling all remaining numbers once a number exceeding the square root<br /> of the maximal number we are interested in is circled (in our example it is &lt;math&gt;5&gt;\sqrt{20}&lt;/math&gt;). The reason is that if a number &lt;math&gt;n&lt;/math&gt; is composite, then it has a prime divisor not exceeding &lt;math&gt;\sqrt n&lt;/math&gt;. <br /> <br /> [[Image:Sieve.PNG|Sieve example for numbers up to 20]]<br /> <br /> ===Related Links===<br /> <br /> * [http://www.math.utah.edu/~pa/Eratosthenes.html Website with good visual example]<br /> <br /> ===See also===<br /> <br /> * [[Number theory]]<br /> * [[Prime]]s</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=File:Sieve.PNG&diff=5885 File:Sieve.PNG 2006-07-03T17:21:52Z <p>Fedja: Eratosthenes sieve</p> <hr /> <div>Eratosthenes sieve</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Principle_of_Inclusion-Exclusion&diff=5865 Talk:Principle of Inclusion-Exclusion 2006-07-03T16:38:46Z <p>Fedja: </p> <hr /> <div>I forgot to write Summary. I added the statement, but it doesn't look very good.<br /> <br /> <br /> It'll look fine after someone adds some more introductory-level information (such as citing a few simpler examples first, before jumping to the semi-general result, which will be indecipherable to a young beginner). Then it will be lower on the page and the big gap won't appear. --[[User:Rrusczyk|Rrusczyk]] 13:25, 18 June 2006 (EDT)<br /> <br /> Adeel, why don't you find the link for your Mathmatical Ideas topic PDF on this and add a link? It might prove useful to anyone beginning combinatorics. --[[User:Mysmartmouth|Mysmartmouth]] 14:35, 18 June 2006 (EDT)<br /> <br /> 5 set example...um, wow... Btw, are you using \mid instead of just | --[[User:Joml88|Joe]] 15:51, 2 July 2006 (EDT)<br /> <br /> ----<br /> <br /> ''143 take scocial studies''. 241 take biology. 300 take history. 213 take algebra and language arts. ''264 take algebra and social studies''. <br /> <br /> He-he, how can that be possible? Someone should better check this monstrous example for other inconsistencies and misprints. Besides, the formulae run away far beyond the screen, which doesn't make it look very pretty. The last remark is that to read the entire problem is quite a boring exercise. On the other hand, it would be a pity to delete it entirely. Maybe we should settle for some 4 set one with similar content? --[[User:Fedja|Fedja]] 12:38, 3 July 2006 (EDT)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Factorial&diff=5841 Talk:Factorial 2006-07-03T13:33:54Z <p>Fedja: </p> <hr /> <div>I added the prime factorization section (needed for Prime Number Theorem and Bertrand postulate). I'm not sure the counting principle I referred to as the ''Lebesgue counting principle'' is not really known under some other name. If you happen to know the correct name for it, please, change the corresponding line.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Factorial&diff=5840 Factorial 2006-07-03T13:30:30Z <p>Fedja: /* Uses */</p> <hr /> <div>The '''factorial''' is an important function in [[combinatorics]] and [[analysis]], used to determine the number of ways to arrange objects.<br /> <br /> === Definition ===<br /> <br /> The factorial is defined for positive integers as &lt;math&gt;n!=n \cdot (n-1) \cdots 2 \cdot 1&lt;/math&gt; Alternatively, a [[recursion|recursive definition]] for the factorial is: &lt;math&gt;n!=n \cdot (n-1)!&lt;/math&gt;.<br /> <br /> === Additional Information ===<br /> <br /> By convention, &lt;math&gt;0!&lt;/math&gt; is given the value &lt;math&gt;1&lt;/math&gt;.<br /> <br /> The [[gamma function]] is a generalization of the factorial to values other than nonnegative integers.<br /> <br /> ===[[Prime factorization]]===<br /> <br /> Since &lt;math&gt;n!&lt;/math&gt; is the product of all positive integers not exceeding &lt;math&gt;n&lt;/math&gt;, it is clear that it is divisible by all<br /> primes &lt;math&gt;p\le n&lt;/math&gt; and not divisible by any prime &lt;math&gt;p&gt;n&lt;/math&gt;. But what is the power of a prime &lt;math&gt;p\le n&lt;/math&gt;<br /> in the prime factorization of &lt;math&gt;n!&lt;/math&gt;? We can find it as the sum of powers of &lt;math&gt;p&lt;/math&gt; in all the factors &lt;math&gt;1,2,\dots, n&lt;/math&gt;<br /> but rather than counting the power of &lt;math&gt;p&lt;/math&gt; in each factor, we shall count the number of factors divisible by a given power of &lt;math&gt;p&lt;/math&gt;. Among the numbers &lt;math&gt;1,2,\dots,n&lt;/math&gt; exactly &lt;math&gt;\left\lfloor\frac n{p^k}\right\rfloor&lt;/math&gt; are divisible by &lt;math&gt;p^k&lt;/math&gt; (here &lt;math&gt;\lfloor\cdot\rfloor&lt;/math&gt; is the [[floor function]]). Now we will use the [[Lebesgue counting principle]] that says that the sum of several non-negative integers &lt;math&gt;a_1,\dots, a_n&lt;/math&gt; (the powers of &lt;math&gt;p&lt;/math&gt; in numbers &lt;math&gt;1,2,\dots,n&lt;/math&gt; in our case) can be found as &lt;math&gt;\sum_{k\ge 1}\#\{j: a_j\ge k\}&lt;/math&gt;. This immediately gives the formula<br /> <br /> &lt;math&gt;\left\lfloor\frac n{p}\right\rfloor+<br /> \left\lfloor\frac n{p^2}\right\rfloor+<br /> \left\lfloor\frac n{p^3}\right\rfloor+\dots&lt;/math&gt;<br /> <br /> for the power of &lt;math&gt;p&lt;/math&gt; in the prime factorization of &lt;math&gt;n!&lt;/math&gt;. The series is formally infinite, but the terms become &lt;math&gt;0&lt;/math&gt; pretty fast. For example, the power of &lt;math&gt;7&lt;/math&gt; in &lt;math&gt;100!&lt;/math&gt; is just<br /> &lt;math&gt;\left\lfloor\frac {100}{7}\right\rfloor+<br /> \left\lfloor\frac {100}{49}\right\rfloor=14+2=16&lt;/math&gt;<br /> (&lt;math&gt;7^3=343&lt;/math&gt; is already greater than &lt;math&gt;100&lt;/math&gt;).<br /> === Uses ===<br /> <br /> The factorial is used in the definitions of [[combinations]] and [[permutations]], as &lt;math&gt;n!&lt;/math&gt; is the number of ways to order &lt;math&gt;n&lt;/math&gt; distinct objects.<br /> <br /> === Examples ===<br /> <br /> * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=508851#p508851 AIME 2003I/1]<br /> <br /> === See also ===<br /> *[[Combinatorics]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Brun%27s_constant&diff=5835 Brun's constant 2006-07-03T01:19:59Z <p>Fedja: /* Proof of convergence */</p> <hr /> <div>==Definition==<br /> <br /> '''Brun's constant''' is the (possibly infinite) sum of [[reciprocal]]s of the [[twin prime]]s &lt;math&gt;\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+\frac{1}{17}+\frac{1}{19}+\cdots&lt;/math&gt;. It turns out that this sum is actually [[convergent]]. Brun's constant is equal to approximately '''&lt;math&gt;1.90216058&lt;/math&gt;'''.<br /> <br /> ==Proof of convergence==<br /> <br /> Everywhere below &lt;math&gt;p&lt;/math&gt; will stand for an odd [[prime number]]. Let <br /> &lt;math&gt;\pi_2(x)=\#\{p\le x:p+2\mathrm{\ is\ also\ prime\,}\}&lt;/math&gt;. We shall prove that &lt;math&gt;\pi_2(x)\le C\frac{x}{(\ln x)^2}(\ln\ln x)^2&lt;/math&gt; for large &lt;math&gt;x&lt;/math&gt; with some absolute constant &lt;math&gt;C&lt;+\infty&lt;/math&gt;.<br /> The technique used in the proof is a version of the [[PIE|inclusion-exclusion principle]] and is known nowadays as '''Brun's simple pure sieve'''. <br /> ====Lemma====<br /> Let &lt;math&gt;a_1,\dots,a_n\in[0,1]&lt;/math&gt;. <br /> Let &lt;math&gt;\sigma_k=\sum_{1\le i_1&lt;\dots&lt;i_k\le n}a_{i_1}\dots a_{i_k}&lt;/math&gt; be the &lt;math&gt;k&lt;/math&gt;-th [[symmetric sum]] of the numbers &lt;math&gt;a_1,\dots, a_n&lt;/math&gt;. Then <br /> &lt;math&gt;1-\sigma_1+\sigma_2-\dots-\sigma_k\le \prod_{j=1}^n(1-a_j)\le 1-\sigma_1+\sigma_2-\dots+\sigma_\ell&lt;/math&gt; for every odd &lt;math&gt;k&lt;/math&gt; and even &lt;math&gt;\ell&lt;/math&gt;.<br /> ====Proof of Lemma====<br /> Induction on &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now take a very big &lt;math&gt;x&lt;/math&gt; and fix some &lt;math&gt;y\le x&lt;/math&gt; to be chosen later. For each odd prime &lt;math&gt;p\le y&lt;/math&gt; let<br /> <br /> &lt;math&gt;A_p=\{n\le x:p|n\mathrm{\ or\ }p|n+2\}&lt;/math&gt;<br /> <br /> Clearly, if &lt;math&gt;n&gt;y&lt;/math&gt;, and &lt;math&gt;n\in A_p&lt;/math&gt; for some &lt;math&gt;p\le y&lt;/math&gt;, then either &lt;math&gt;n&lt;/math&gt; or &lt;math&gt;n+2&lt;/math&gt; is <br /> not prime. Thus, the number of primes &lt;math&gt;q\le x&lt;/math&gt; such that &lt;math&gt;q+2&lt;/math&gt; is also prime does not exceed <br /> &lt;math&gt;y+\left(x-\left|\bigcup_{p\le y}A_p\right|\right)&lt;/math&gt;.<br /> <br /> Let now &lt;math&gt;\ell&lt;/math&gt; be an even number. By the inclusion-exclusion principle, <br /> <br /> &lt;math&gt; \left|\bigcup_{p\le y}A_p\right|\ge<br /> \sum_{p\le y}|A_p|-<br /> \sum_{p_1&lt;p_2\le y}|A_{p_1}\cap A_{p_2}|+<br /> \sum_{p_1&lt;p_2&lt;p_3\le y}|A_{p_1}\cap A_{p_2}\cap A_{p_3}|-<br /> \dots<br /> -<br /> \sum_{p_1&lt;\dots&lt;p_\ell\le y}|A_{p_1}\cap\dots\cap A_{p_\ell}|<br /> &lt;/math&gt;<br /> <br /> Let us now estimate &lt;math&gt;|A_{p_1}\cap\dots\cap A_{p_j}|&lt;/math&gt;.<br /> Note that the condition &lt;math&gt;n\in A_{p_1}\cap\dots\cap A_{p_j} &lt;/math&gt;<br /> depends only on the [[remainder]] of &lt;math&gt;n&lt;/math&gt; modulo &lt;math&gt;p_1\cdot\dots\cdot p_j&lt;/math&gt; and that, by the [[Chinese Remainder Theorem]], there are exactly &lt;math&gt;2^j&lt;/math&gt;<br /> remainders that satisfy this condition (for each &lt;math&gt;p_i\,&lt;/math&gt;, we must have &lt;math&gt;n\equiv 0\mod p_i&lt;/math&gt; or &lt;math&gt;n\equiv -2\mod p_i&lt;/math&gt; and the remainders for different &lt;math&gt;p_i\,&lt;/math&gt;<br /> can be chosen independently). Therefore<br /> <br /> &lt;math&gt;|A_{p_1}\cap\dots\cap A_{p_j}|=\frac{2^j x}{p_1\cdot\dots\cdot p_j}+R(p_1,\dots,p_j)&lt;/math&gt;<br /> <br /> where &lt;math&gt;|R(p_1,\dots,p_j)|\le 2^j&lt;/math&gt;.<br /> It follows that <br /> <br /> &lt;math&gt;x-\left|\bigcup_{p\le y}A_p\right|\le x(1-\sigma_1+\sigma_2-\dots+\sigma_\ell)+y^{\ell}&lt;/math&gt;<br /> <br /> where &lt;math&gt;\sigma_k&lt;/math&gt; is the &lt;math&gt;k&lt;/math&gt;-th symmetric sum of the set &lt;math&gt;\left\{\frac 2p:p\le y\right\}&lt;/math&gt;. Indeed, we have not more than &lt;math&gt;\left(\frac y2\right)^\ell&lt;/math&gt; terms in the inclusion-exclusion formula above and each term is estimated with an error not greater than &lt;math&gt;2^\ell&lt;/math&gt;.<br /> <br /> Now notice that &lt;math&gt;1-\sigma_1+\sigma_2-\dots+\sigma_\ell=<br /> (1-\sigma_1+\sigma_2-\dots-\sigma_{\ell-1})+\sigma_\ell\le<br /> \prod_{p\le y}\left(1-\frac 2p\right)+\sigma_\ell&lt;/math&gt;<br /> by the lemma.<br /> The product does not exceed &lt;math&gt;\prod_{p\le y}\left(1-\frac 1p\right)^2\le\frac {C}{(\ln y)^2}&lt;/math&gt; (see the [[prime number]] article), so it remains to estimate &lt;math&gt;\sigma_\ell&lt;/math&gt;. But we have<br /> <br /> &lt;math&gt;\sigma_\ell\le \frac{1}{\ell!}\left(\sum_{p\le y}\frac 2p\right)^\ell\le\frac 1{\ell!}(2e\ln\ln y)^\ell\le<br /> \left(\frac{2e^2\ln\ln x}{\ell}\right)^\ell<br /> &lt;/math&gt;<br /> <br /> This estimate yields the final inequality<br /> <br /> &lt;math&gt;\pi_2(x)\le y+ x\left[\frac C{(\ln y)^2}<br /> +\left(\frac {2e^2\ln\ln x}{\ell}\right)^\ell\right]+y^\ell&lt;/math&gt;<br /> <br /> It remains to minimize the right hand side over all possible choices of <br /> &lt;math&gt;y&lt;/math&gt; and &lt;math&gt;\ell&lt;/math&gt;. We shall choose &lt;math&gt;\ell\approx 4e^2\ln\ln x&lt;/math&gt; and &lt;math&gt;y=x^{\frac 1{100\ln\ln x}}&lt;/math&gt;. With this choice, every term on the right does not exceed &lt;math&gt;C\frac{x}{(\ln x)^2}(\ln\ln x)^2&lt;/math&gt; and we are done.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Brun%27s_constant&diff=5816 Brun's constant 2006-07-02T20:03:09Z <p>Fedja: added a proof of Brun's theorem</p> <hr /> <div>==Definition==<br /> <br /> '''Brun's constant''' is the (possibly infinite) sum of [[reciprocal]]s of the [[twin prime]]s &lt;math&gt;\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+\frac{1}{17}+\frac{1}{19}+\cdots&lt;/math&gt;. It turns out that this sum is actually [[convergent]]. Brun's constant is equal to approximately '''&lt;math&gt;1.90216058&lt;/math&gt;'''.<br /> <br /> ==Proof of convergence==<br /> <br /> Everywhere below &lt;math&gt;p&lt;/math&gt; will stand for an odd [[prime number]]. Let <br /> &lt;math&gt;\pi_2(x)=\#\{p:p+2\mathrm{\ is\ also\ prime\,}\}&lt;/math&gt;. We shall prove that &lt;math&gt;\pi_2(x)\le C\frac{x}{(\ln x)^2}(\ln\ln x)^2&lt;/math&gt; for large &lt;math&gt;x&lt;/math&gt; with some absolute constant &lt;math&gt;C&lt;+\infty&lt;/math&gt;.<br /> The technique used in the proof is a version of the [[PIE|inclusion-exclusion principle]] and is known nowadays as '''Brun's simple pure sieve'''. <br /> ====Lemma====<br /> Let &lt;math&gt;a_1,\dots,a_n\in[0,1]&lt;/math&gt;. <br /> Let &lt;math&gt;\sigma_k=\sum_{1\le i_1&lt;\dots&lt;i_k\le n}a_{i_1}\dots a_{i_k}&lt;/math&gt; be the &lt;math&gt;k&lt;/math&gt;-th [[symmetric sum]] of the numbers &lt;math&gt;a_1,\dots, a_n&lt;/math&gt;. Then <br /> &lt;math&gt;1-\sigma_1+\sigma_2-\dots-\sigma_k\le \prod_{j=1}^n(1-a_j)\le 1-\sigma_1+\sigma_2-\dots+\sigma_\ell&lt;/math&gt; for every odd &lt;math&gt;k&lt;/math&gt; and even &lt;math&gt;\ell&lt;/math&gt;.<br /> ====Proof of Lemma====<br /> Induction on &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now take a very big &lt;math&gt;x&lt;/math&gt; and fix some &lt;math&gt;y\le x&lt;/math&gt; to be chosen later. For each odd prime &lt;math&gt;p\le y&lt;/math&gt; let<br /> <br /> &lt;math&gt;A_p=\{n\le x:p|n\mathrm{\ or\ }p|n+2\}&lt;/math&gt;<br /> <br /> Clearly, if &lt;math&gt;n&gt;y&lt;/math&gt;, and &lt;math&gt;n\in A_p&lt;/math&gt; for some &lt;math&gt;p\le y&lt;/math&gt;, then either &lt;math&gt;n&lt;/math&gt; or &lt;math&gt;n+2&lt;/math&gt; is <br /> not prime. Thus, the number of primes &lt;math&gt;q\le x&lt;/math&gt; such that &lt;math&gt;q+2&lt;/math&gt; is also prime does not exceed <br /> &lt;math&gt;y+\left(x-\left|\bigcup_{p\le y}A_p\right|\right)&lt;/math&gt;.<br /> <br /> Let now &lt;math&gt;\ell&lt;/math&gt; be an even number. By the inclusion-exclusion principle, <br /> <br /> &lt;math&gt; \left|\bigcup_{p\le y}A_p\right|\ge<br /> \sum_{p\le y}|A_p|-<br /> \sum_{p_1&lt;p_2\le y}|A_{p_1}\cap A_{p_2}|+<br /> \sum_{p_1&lt;p_2&lt;p_3\le y}|A_{p_1}\cap A_{p_2}\cap A_{p_3}|-<br /> \dots<br /> -<br /> \sum_{p_1&lt;\dots&lt;p_\ell\le y}|A_{p_1}\cap\dots\cap A_{p_\ell}|<br /> &lt;/math&gt;<br /> <br /> Let us now estimate &lt;math&gt;|A_{p_1}\cap\dots\cap A_{p_j}|&lt;/math&gt;.<br /> Note that the condition &lt;math&gt;n\in A_{p_1}\cap\dots\cap A_{p_j} &lt;/math&gt;<br /> depends only on the [[remainder]] of &lt;math&gt;n&lt;/math&gt; modulo &lt;math&gt;p_1\cdot\dots\cdot p_j&lt;/math&gt; and that, by the [[Chinese Remainder Theorem]], there are exactly &lt;math&gt;2^j&lt;/math&gt;<br /> remainders that satisfy this condition (for each &lt;math&gt;p_i\,&lt;/math&gt;, we must have &lt;math&gt;n\equiv 0\mod p_i&lt;/math&gt; or &lt;math&gt;n\equiv -2\mod p_i&lt;/math&gt; and the remainders for different &lt;math&gt;p_i\,&lt;/math&gt;<br /> can be chosen independently). Therefore<br /> <br /> &lt;math&gt;|A_{p_1}\cap\dots\cap A_{p_j}|=\frac{2^j x}{p_1\cdot\dots\cdot p_j}+R(p_1,\dots,p_j)&lt;/math&gt;<br /> <br /> where &lt;math&gt;|R(p_1,\dots,p_j)|\le 2^j&lt;/math&gt;.<br /> It follows that <br /> <br /> &lt;math&gt;x-\left|\bigcup_{p\le y}A_p\right|\le x(1-\sigma_1+\sigma_2-\dots+\sigma_\ell)+y^{\ell}&lt;/math&gt;<br /> <br /> where &lt;math&gt;\sigma_k&lt;/math&gt; is the &lt;math&gt;k&lt;/math&gt;-th symmetric sum of the set &lt;math&gt;\left\{\frac 2p:p\le y\right\}&lt;/math&gt;. Indeed, we have not more than &lt;math&gt;\left(\frac y2\right)^\ell&lt;/math&gt; terms in the inclusion-exclusion formula above and each term is estimated with an error not greater than &lt;math&gt;2^\ell&lt;/math&gt;.<br /> <br /> Now notice that &lt;math&gt;1-\sigma_1+\sigma_2-\dots+\sigma_\ell=<br /> (1-\sigma_1+\sigma_2-\dots-\sigma_{\ell-1})+\sigma_\ell\le<br /> \prod_{p\le y}\left(1-\frac 2p\right)+\sigma_\ell&lt;/math&gt;<br /> by the lemma.<br /> The product does not exceed &lt;math&gt;\prod_{p\le y}\left(1-\frac 1p\right)^2\le\frac {C}{(\ln y)^2}&lt;/math&gt; (see the [[prime number]] article), so it remains to estimate &lt;math&gt;\sigma_\ell&lt;/math&gt;. But we have<br /> <br /> &lt;math&gt;\sigma_\ell\le \frac{1}{\ell!}\left(\sum_{p\le y}\frac 2p\right)^\ell\le\frac 1{\ell!}(2e\ln\ln y)^\ell\le<br /> \left(\frac{2e^2\ln\ln x}{\ell}\right)^\ell<br /> &lt;/math&gt;<br /> <br /> This estimate yields the final inequality<br /> <br /> &lt;math&gt;\pi_2(x)\le y+ x\left[\frac C{(\ln y)^2}<br /> +\left(\frac {2e^2\ln\ln x}{\ell}\right)^\ell\right]+y^\ell&lt;/math&gt;<br /> <br /> It remains to minimize the right hand side over all possible choices of <br /> &lt;math&gt;y&lt;/math&gt; and &lt;math&gt;\ell&lt;/math&gt;. We shall choose &lt;math&gt;\ell\approx 4e^2\ln\ln x&lt;/math&gt; and &lt;math&gt;y=x^{\frac 1{100\ln\ln x}}&lt;/math&gt;. With this choice, every term on the right does not exceed &lt;math&gt;C\frac{x}{(\ln x)^2}(\ln\ln x)^2&lt;/math&gt; and we are done.</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Prime_Number_Theorem&diff=5776 Prime Number Theorem 2006-07-01T19:03:51Z <p>Fedja: /* Connection with Riemann zeta function */</p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> The aim of this article is to present the proof of the '''prime number theorem''' that says that the number &lt;math&gt;\pi(n)&lt;/math&gt; of [[prime]]s not exceeding &lt;math&gt;n&lt;/math&gt; is approximately &lt;math&gt;\frac n{\ln n}&lt;/math&gt; or, more precisely, that<br /> <br /> &lt;math&gt;\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.&lt;/math&gt;<br /> <br /> Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material. <br /> <br /> We shall start with some elementary observations due to Chebyshev. <br /> ==Chebyshev's estimates==<br /> The key observation is that &lt;math&gt;{2m\choose m}=\frac{(2m)!}{(m!)^2}&lt;/math&gt; is divisible by all primes &lt;math&gt;p&lt;/math&gt; satisfying &lt;math&gt;m&lt;p\le 2m&lt;/math&gt;. Indeed, every such prime appears in the numerator &lt;math&gt;(2m)!&lt;/math&gt; and does not appear in the denominator &lt;math&gt;(m!)^2&lt;/math&gt;. Thus, &lt;math&gt;\prod_{m&lt;p\le 2m}p\le {2m\choose m}\le 2^{2m}&lt;/math&gt; (from now on, &lt;math&gt;p&lt;/math&gt; will always stand for a prime number, so, to shorten the notation, we will not explicitly write &quot;&lt;math&gt;p&lt;/math&gt; is prime&quot; in the descriptions of sum and product ranges). Similarly, considering &lt;math&gt;{2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}&lt;/math&gt;, we see that <br /> &lt;math&gt;\prod_{m+1&lt;p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}&lt;/math&gt; (the last inequality holds because &lt;math&gt;{2m+1\choose m}={2m+1\choose m+1}&lt;/math&gt; and &lt;math&gt;{2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}&lt;/math&gt;). Now we are ready to prove the <br /> ===Upper bound for the product of primes===<br /> ====Lemma 1====<br /> For every positive integer &lt;math&gt;n&lt;/math&gt;, we have<br /> &lt;math&gt;\prod_{p\le n}p\le 4^n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 1====<br /> [[Induction]] on &lt;math&gt;n&lt;/math&gt;. The base &lt;math&gt;n=1&lt;/math&gt; is obvious. Suppose now that the statement holds for all numbers strictly less than &lt;math&gt;n&lt;/math&gt;. If &lt;math&gt;n=2m&lt;/math&gt; is even, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m}p\right)\cdot \left(\prod_{m&lt;p\le 2m}p\right)\le<br /> 4^m 2^{2m}=4^{2m}=4^n.<br /> &lt;/math&gt;<br /> <br /> If &lt;math&gt;n=2m+1&lt;/math&gt; is odd, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m+1}p\right)\cdot \left(\prod_{m+1&lt;p\le 2m+1}p\right)\le<br /> 4^{m+1} 2^{2m}=4^{2m+1}=4^n.<br /> &lt;/math&gt;<br /> ----<br /> From this lemma we can easily derive the <br /> ===Upper bound for the number of primes===<br /> ====Lemma 2====<br /> &lt;math&gt;\pi(n)\le 4\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 1 as &lt;math&gt;\sum_{p\le n}\ln p\le n\ln 4&lt;/math&gt;. It follows that<br /> &lt;math&gt;\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n&lt;p&lt;n}\ln p\le n\ln 4&lt;/math&gt;.<br /> But then &lt;math&gt;\pi(n)\le 2\ln 4\frac{n}{\ln n}+\pi(\sqrt n)\le 2\ln 4\,\frac{n}{\ln n}+\sqrt n&lt; 4\frac{n}{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. <br /> ===Lower bound for the product of primes===<br /> ====Lemma 3====<br /> &lt;math&gt;\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}&lt;/math&gt;.<br /> <br /> ====Proof of Lemma 3====<br /> The idea is again to investigate the [[prime factorization]] of <br /> &lt;math&gt;{n\choose \lfloor \frac n2 \rfloor}&lt;/math&gt;. We shall give the proof for odd &lt;math&gt;n=2m+1&lt;/math&gt; (the case of even &lt;math&gt;n&lt;/math&gt; is similar). Recall that the power in which a prime number &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;\ell!&lt;/math&gt; equals &lt;math&gt;\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots&lt;/math&gt; (see [[factorial]] for the proof).<br /> Therefore, the power in which &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;{n\choose m}&lt;/math&gt; equals &lt;math&gt;\sum_{k\ge 1}\left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac m{p^k}\right\rfloor-\left\lfloor \frac {m+1}{p^k}\right\rfloor\right)&lt;/math&gt; Note that each term in the last sum does not exceed &lt;math&gt;1&lt;/math&gt; and the number of non-zero terms does not exceed &lt;math&gt;\left\lfloor {\log_p n}\right\rfloor&lt;/math&gt;, which is &lt;math&gt;1&lt;/math&gt; for all &lt;math&gt;\sqrt n&lt;p\le n&lt;/math&gt;.<br /> Hence <br /> <br /> &lt;math&gt;{n\choose m}\le \left(\prod_{\sqrt n&lt;p\le n}p\right)\cdot\left(\prod_{p\le \sqrt n}p^{\lfloor\log_p n\rfloor}\right)\le \left(\prod_{p\le n}p\right)\cdot n^{\pi(\sqrt n)}\le n^{\sqrt n}\cdot \prod_{p\le n}p&lt;/math&gt;.<br /> <br /> On the other hand, &lt;math&gt;{n\choose m}&lt;/math&gt; is the largest of the &lt;math&gt;n+1&lt;/math&gt; binomial coefficients whose sum is &lt;math&gt;2^n&lt;/math&gt;. Thus, &lt;math&gt;{n\choose m}\ge \frac{2^n}{(n+1)}&lt;/math&gt; whence the estimate of the lemma.<br /> ===Lower bound for the number of primes===<br /> ====Lemma 4====<br /> &lt;math&gt;\pi(n)\ge \frac 12\,\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 3 as &lt;math&gt;\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n &gt; \frac 12 n&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;. <br /> But the left hand side does not exceed &lt;math&gt;\pi(n)\ln n&lt;/math&gt; whence the lemma.<br /> <br /> ----<br /> We haven't proved the prime number theorem yet, but we showed that <br /> &lt;math&gt;\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}&lt;/math&gt;<br /> for all sufficiently large &lt;math&gt;n&lt;/math&gt;. For many readers it is probably a good idea to stop here and to proceed to [[Bertrand's postulate]]. The material below this point requires good knowledge of analysis and is, probably, accessible to college students only.<br /> <br /> ==Von Mangoldt function and reformulation of the prime number theorem==<br /> <br /> For a positive integer &lt;math&gt;n&lt;/math&gt;, define &lt;math&gt;\Lambda(n)=\ln p&lt;/math&gt; if &lt;math&gt;n&lt;/math&gt; is a pure positive integer power of a prime &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;\Lambda(n)=0&lt;/math&gt; otherwise (so &lt;math&gt;\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2&lt;/math&gt;, &lt;math&gt;\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3&lt;/math&gt; and so on. Let &lt;math&gt;\psi(x)=\sum_{n\le x}\Lambda(n)&lt;/math&gt; <br /> ====Lemma 5====<br /> The prime number theorem is equivalent to &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> ====Proof of Lemma 5====<br /> Note that for &lt;math&gt;x\ge 1&lt;/math&gt;, we have &lt;math&gt;\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p&lt;/math&gt;. Since &lt;math&gt;\lfloor \log_p x\rfloor\ln p\le \ln x&lt;/math&gt;, we immediately get &lt;math&gt;\psi(x)\le \pi(x)\ln x&lt;/math&gt;. Let now &lt;math&gt;\alpha&lt;1&lt;/math&gt;. For &lt;math&gt;x^\alpha&lt;p\le x&lt;/math&gt;, we have &lt;math&gt;\ln p\ge \alpha \ln x&lt;/math&gt; and, therefore, &lt;math&gt;\psi(x)\ge \sum_{x^\alpha&lt;p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x&lt;/math&gt;, which can be rewritten as &lt;math&gt;\pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> \pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;.&lt;/math&gt; <br /> <br /> Assume now that we know that &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> Dividing by &lt;math&gt;x&lt;/math&gt; and passing to the limit as &lt;math&gt;x\to+\infty&lt;/math&gt;, we get<br /> <br /> &lt;math&gt;1\le\liminf_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le \limsup_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le\frac 1\alpha\,.&lt;/math&gt;<br /> <br /> Since it is true for all &lt;math&gt;\alpha&lt;1&lt;/math&gt;, we conclude that<br /> &lt;math&gt;\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1&lt;/math&gt;. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise.<br /> <br /> ==Connection with Riemann [[zeta function]]==<br /> Write &lt;math&gt;\zeta&lt;/math&gt;-function as the Euler product &lt;math&gt;\zeta(s)=\prod_p (1-p^{-s})^{-1}&lt;/math&gt; and take minus logarithmic derivative of both sides. We'll get the formula<br /> <br /> &lt;math&gt;-\frac{\zeta'(s)}{\zeta(s)}=\sum_p\frac {p^{-s}\ln p}{1-p^{-s}}=\sum_p\sum_{k\ge 1}\frac{\ln p}{p^{ks}}=\sum_{n\ge 1}\frac {\Lambda(n)}{n^s}=\int_1^\infty \frac{d\psi(x)}{x^s}<br /> =s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}&lt;/math&gt;<br /> <br /> if &lt;math&gt;\Re s&gt;1&lt;/math&gt;<br /> <br /> Let now &lt;math&gt;\xi(t)=\frac{\psi(e^t)}{e^t}-1&lt;/math&gt;. Then, making the change of variable &lt;math&gt;x=e^t&lt;/math&gt; in the last integral, we get<br /> <br /> &lt;math&gt;\int_{0}^\infty \xi(t)e^{-(s-1)t}\,dt=-\frac{\zeta'(s)}{s\zeta(s)}-\frac 1{s-1}&lt;/math&gt; <br /> for all &lt;math&gt;s&lt;/math&gt; with &lt;math&gt;\Re s&gt;1&lt;/math&gt;.<br /> <br /> Since the &lt;math&gt;\zeta&lt;/math&gt;-function has a simple pole at &lt;math&gt;s=1&lt;/math&gt; and no zeroes on the line &lt;math&gt;\Re s=1&lt;/math&gt;, the right hand side represents a function [[analytic]] in some domain containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 1\}&lt;/math&gt;<br /> <br /> By the Chebyshev's estimates, we have &lt;math&gt;-1\le\xi(t)\le 3&lt;/math&gt;, so &lt;math&gt;\xi(t)&lt;/math&gt; is bounded and we can apply [[Newman's Tauberian Theorem]] and conclude that &lt;math&gt;\int_0^\infty \xi(t)\,dt&lt;/math&gt; converges. <br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Prime_Number_Theorem&diff=5468 Prime Number Theorem 2006-06-30T17:57:56Z <p>Fedja: /* Connection with Riemann zeta function */</p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> The aim of this article is to present the proof of the '''prime number theorem''' that says that the number &lt;math&gt;\pi(n)&lt;/math&gt; of [[prime]]s not exceeding &lt;math&gt;n&lt;/math&gt; is approximately &lt;math&gt;\frac n{\ln n}&lt;/math&gt; or, more precisely, that<br /> <br /> &lt;math&gt;\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.&lt;/math&gt;<br /> <br /> Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material. <br /> <br /> We shall start with some elementary observations due to Chebyshev. <br /> ==Chebyshev's estimates==<br /> The key observation is that &lt;math&gt;{2m\choose m}=\frac{(2m)!}{(m!)^2}&lt;/math&gt; is divisible by all primes &lt;math&gt;p&lt;/math&gt; satisfying &lt;math&gt;m&lt;p\le 2m&lt;/math&gt;. Indeed, every such prime appears in the numerator &lt;math&gt;(2m)!&lt;/math&gt; and does not appear in the denominator &lt;math&gt;(m!)^2&lt;/math&gt;. Thus, &lt;math&gt;\prod_{m&lt;p\le 2m}p\le {2m\choose m}\le 2^{2m}&lt;/math&gt; (from now on, &lt;math&gt;p&lt;/math&gt; will always stand for a prime number, so, to shorten the notation, we will not explicitly write &quot;&lt;math&gt;p&lt;/math&gt; is prime&quot; in the descriptions of sum and product ranges). Similarly, considering &lt;math&gt;{2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}&lt;/math&gt;, we see that <br /> &lt;math&gt;\prod_{m+1&lt;p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}&lt;/math&gt; (the last inequality holds because &lt;math&gt;{2m+1\choose m}={2m+1\choose m+1}&lt;/math&gt; and &lt;math&gt;{2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}&lt;/math&gt;). Now we are ready to prove the <br /> ===Upper bound for the product of primes===<br /> ====Lemma 1====<br /> For every positive integer &lt;math&gt;n&lt;/math&gt;, we have<br /> &lt;math&gt;\prod_{p\le n}p\le 4^n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 1====<br /> [[Induction]] on &lt;math&gt;n&lt;/math&gt;. The base &lt;math&gt;n=1&lt;/math&gt; is obvious. Suppose now that the statement holds for all numbers strictly less than &lt;math&gt;n&lt;/math&gt;. If &lt;math&gt;n=2m&lt;/math&gt; is even, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m}p\right)\cdot \left(\prod_{m&lt;p\le 2m}p\right)\le<br /> 4^m 2^{2m}=4^{2m}=4^n.<br /> &lt;/math&gt;<br /> <br /> If &lt;math&gt;n=2m+1&lt;/math&gt; is odd, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m+1}p\right)\cdot \left(\prod_{m+1&lt;p\le 2m+1}p\right)\le<br /> 4^{m+1} 2^{2m}=4^{2m+1}=4^n.<br /> &lt;/math&gt;<br /> ----<br /> From this lemma we can easily derive the <br /> ===Upper bound for the number of primes===<br /> ====Lemma 2====<br /> &lt;math&gt;\pi(n)\le 4\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 1 as &lt;math&gt;\sum_{p\le n}\ln p\le n\ln 4&lt;/math&gt;. It follows that<br /> &lt;math&gt;\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n&lt;p&lt;n}\ln p\le n\ln 4&lt;/math&gt;.<br /> But then &lt;math&gt;\pi(n)\le 2\ln 4\frac{n}{\ln n}+\pi(\sqrt n)\le 2\ln 4\,\frac{n}{\ln n}+\sqrt n&lt; 4\frac{n}{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. <br /> ===Lower bound for the product of primes===<br /> ====Lemma 3====<br /> &lt;math&gt;\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}&lt;/math&gt;.<br /> <br /> ====Proof of Lemma 3====<br /> The idea is again to investigate the [[prime factorization]] of <br /> &lt;math&gt;{n\choose \lfloor \frac n2 \rfloor}&lt;/math&gt;. We shall give the proof for odd &lt;math&gt;n=2m+1&lt;/math&gt; (the case of even &lt;math&gt;n&lt;/math&gt; is similar). Recall that the power in which a prime number &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;\ell!&lt;/math&gt; equals &lt;math&gt;\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots&lt;/math&gt; (see [[factorial]] for the proof).<br /> Therefore, the power in which &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;{n\choose m}&lt;/math&gt; equals &lt;math&gt;\sum_{k\ge 1}\left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac m{p^k}\right\rfloor-\left\lfloor \frac {m+1}{p^k}\right\rfloor\right)&lt;/math&gt; Note that each term in the last sum does not exceed &lt;math&gt;1&lt;/math&gt; and the number of non-zero terms does not exceed &lt;math&gt;\left\lfloor {\log_p n}\right\rfloor&lt;/math&gt;, which is &lt;math&gt;1&lt;/math&gt; for all &lt;math&gt;\sqrt n&lt;p\le n&lt;/math&gt;.<br /> Hence <br /> <br /> &lt;math&gt;{n\choose m}\le \left(\prod_{\sqrt n&lt;p\le n}p\right)\cdot\left(\prod_{p\le \sqrt n}p^{\lfloor\log_p n\rfloor}\right)\le \left(\prod_{p\le n}p\right)\cdot n^{\pi(\sqrt n)}\le n^{\sqrt n}\cdot \prod_{p\le n}p&lt;/math&gt;.<br /> <br /> On the other hand, &lt;math&gt;{n\choose m}&lt;/math&gt; is the largest of the &lt;math&gt;n+1&lt;/math&gt; binomial coefficients whose sum is &lt;math&gt;2^n&lt;/math&gt;. Thus, &lt;math&gt;{n\choose m}\ge \frac{2^n}{(n+1)}&lt;/math&gt; whence the estimate of the lemma.<br /> ===Lower bound for the number of primes===<br /> ====Lemma 4====<br /> &lt;math&gt;\pi(n)\ge \frac 12\,\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 3 as &lt;math&gt;\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n &gt; \frac 12 n&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;. <br /> But the left hand side does not exceed &lt;math&gt;\pi(n)\ln n&lt;/math&gt; whence the lemma.<br /> <br /> ----<br /> We haven't proved the prime number theorem yet, but we showed that <br /> &lt;math&gt;\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}&lt;/math&gt;<br /> for all sufficiently large &lt;math&gt;n&lt;/math&gt;. For many readers it is probably a good idea to stop here and to proceed to [[Bertrand's postulate]]. The material below this point requires good knowledge of analysis and is, probably, accessible to college students only.<br /> <br /> ==Von Mangoldt function and reformulation of the prime number theorem==<br /> <br /> For a positive integer &lt;math&gt;n&lt;/math&gt;, define &lt;math&gt;\Lambda(n)=\ln p&lt;/math&gt; if &lt;math&gt;n&lt;/math&gt; is a pure positive integer power of a prime &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;\Lambda(n)=0&lt;/math&gt; otherwise (so &lt;math&gt;\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2&lt;/math&gt;, &lt;math&gt;\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3&lt;/math&gt; and so on. Let &lt;math&gt;\psi(x)=\sum_{n\le x}\Lambda(n)&lt;/math&gt; <br /> ====Lemma 5====<br /> The prime number theorem is equivalent to &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> ====Proof of Lemma 5====<br /> Note that for &lt;math&gt;x\ge 1&lt;/math&gt;, we have &lt;math&gt;\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p&lt;/math&gt;. Since &lt;math&gt;\lfloor \log_p x\rfloor\ln p\le \ln x&lt;/math&gt;, we immediately get &lt;math&gt;\psi(x)\le \pi(x)\ln x&lt;/math&gt;. Let now &lt;math&gt;\alpha&lt;1&lt;/math&gt;. For &lt;math&gt;x^\alpha&lt;p\le x&lt;/math&gt;, we have &lt;math&gt;\ln p\ge \alpha \ln x&lt;/math&gt; and, therefore, &lt;math&gt;\psi(x)\ge \sum_{x^\alpha&lt;p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x&lt;/math&gt;, which can be rewritten as &lt;math&gt;\pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> \pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;.&lt;/math&gt; <br /> <br /> Assume now that we know that &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> Dividing by &lt;math&gt;x&lt;/math&gt; and passing to the limit as &lt;math&gt;x\to+\infty&lt;/math&gt;, we get<br /> <br /> &lt;math&gt;1\le\liminf_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le \limsup_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le\frac 1\alpha\,.&lt;/math&gt;<br /> <br /> Since it is true for all &lt;math&gt;\alpha&lt;1&lt;/math&gt;, we conclude that<br /> &lt;math&gt;\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1&lt;/math&gt;. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise.<br /> <br /> ==Connection with Riemann [[zeta function]]==<br /> Write &lt;math&gt;\zeta&lt;/math&gt;-function as the Euler product &lt;math&gt;\zeta(s)=\prod_p (1-p^{-s})^{-1}&lt;/math&gt; and take minus logarithmic derivative of both sides. We'll get the formula<br /> <br /> &lt;math&gt;-\frac{\zeta'(s)}{\zeta(s)}=\sum_p\frac {p^{-s}\ln p}{1-p^{-s}}=\sum_p\sum_{k\ge 1}\frac{\ln p}{p^{ks}}=\sum_{n\ge 1}\frac {\Lambda(n)}{n^s}=\int_1^\infty \frac{d\psi(x)}{x^s}<br /> =s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}&lt;/math&gt;<br /> <br /> if &lt;math&gt;\Re s&gt;1&lt;/math&gt;<br /> <br /> Let now &lt;math&gt;\xi(t)=\frac{\psi(e^t)}{e^t}-1&lt;/math&gt;. Then, making the change of variable &lt;math&gt;x=e^t&lt;/math&gt; in the last integral, we get<br /> <br /> &lt;math&gt;\int_{0}^\infty \xi(t)e^{-(s-1)t}\,dt=-\frac{\zeta'(s)}{s\zeta(s)}-\frac 1{s-1}&lt;/math&gt; <br /> for all &lt;math&gt;s&lt;/math&gt; with &lt;math&gt;\Re s&gt;1&lt;/math&gt;.<br /> <br /> Since the &lt;math&gt;\zeta&lt;/math&gt;-function has a simple pole at &lt;math&gt;s=1&lt;/math&gt; and no zeroes on the line &lt;math&gt;\Re s=1&lt;/math&gt;, the right hand side represents a function [[analytic]] in some domain containing the closed half-plane &lt;math&gt;\{s\in\mathbb C\,:\,\Re s\ge 1\}&lt;/math&gt;<br /> <br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion&diff=5386 Principle of Inclusion-Exclusion 2006-06-30T01:48:14Z <p>Fedja: /* Statement */</p> <hr /> <div>== Introduction ==<br /> The '''Principle of Inclusion-Exclusion''' (abbreviated PIE) provides an organized method/formula to find the number of [[elements]] in the [[union]] of a given group of [[sets]], the size of each set, and the size of all possible intersections among the sets.<br /> <br /> === Two Set Example ===<br /> Assume we are given the sizes of two sets, &lt;math&gt;|A_1|&lt;/math&gt; and &lt;math&gt;|A_2|&lt;/math&gt; and the size of their [[intersection]], &lt;math&gt;|A_1\cap A_2|&lt;/math&gt;. We wish to find the size of their union, &lt;math&gt;|A_1\cup A_2|&lt;/math&gt;.<br /> <br /> To find the union, we can add &lt;math&gt;|A_1|&lt;/math&gt; and &lt;math&gt;|A_2|&lt;/math&gt;. In doing so, we know we have counted everything in &lt;math&gt;|A_1\cup A_2|&lt;/math&gt; at least once. However, some things were counted twice. The elements that were counted twice are precisely those in &lt;math&gt; {}A_1\cap A_2 &lt;/math&gt;. Thus, we have that:<br /> <br /> &lt;center&gt;&lt;math&gt; |A_1 \cup A_2| = |A_1| + |A_2| - |A_1\cap A_2|. &lt;/math&gt;&lt;/center&gt;<br /> <br /> === Three Set Example ===<br /> Assume we are given the sizes of three sets, &lt;math&gt;|A_1|, |A_2|,{}&lt;/math&gt; and &lt;math&gt;|A_3|&lt;/math&gt;, the size of their pairwise intersections, &lt;math&gt;|A_1\cap A_2|, |A_2\cap A_3|&lt;/math&gt; and &lt;math&gt;|A_3\cap A_1|&lt;/math&gt;, and the size their overall intersection, &lt;math&gt;|A_1\cap A_2\cap A_3|&lt;/math&gt;. We wish to find the size of their union, &lt;math&gt;|A_1\cup A_2\cup A_3|&lt;/math&gt;.<br /> <br /> Just like in the Two Set Example, we start with the sum of the sizes of the individual sets &lt;math&gt;|A_1|+|A_2|+|A_3|&lt;/math&gt;. We have counted the elements which are in exactly one of the original three sets once, but we've obviously counted other things twice, and even other things thrice! To account for the elements that are in two of the three sets, we first subtract out &lt;math&gt;|A_1\cap A_2|+|A_2\cap A_3| + |A_3\cap A_1|&lt;/math&gt;. Now we have correctly accounted for them since we counted them twice originally, and just subtracted them out once. However, the elements that are in all three sets were originally counted three times, and then subtracted out three times. We have to add back in &lt;math&gt;|A_1\cap A_2\cap A_3|&lt;/math&gt;. Putting this all together gives:<br /> <br /> &lt;center&gt;&lt;math&gt; |A_1\cup A_2\cup A_3| = |A_1| + |A_2| + |A_3| -|A_1\cap A_2| - |A_2\cap A_3| - |A_3\cap A_1| +|A_1\cap A_2\cap A_3|.&lt;/math&gt;&lt;/center&gt;<br /> <br /> == Statement ==<br /> If &lt;math&gt;(A_i)_{1\leq i\leq n}&lt;/math&gt; are finite sets, then:<br /> &lt;center&gt;&lt;math&gt; \left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|<br /> -\sum_{i &lt; j}\left|A_i\cap A_j\right| +\sum_{i&lt;j&lt;k}\left|A_i\cap A_j\cap A_k\right|-\cdots\ +(-1)^n \left|A_1\cap\cdots\cap A_n\right|{}. &lt;/math&gt;&lt;/center&gt;<br /> == Remark ==<br /> Sometimes it is also useful to know that, if you take into account only the first &lt;math&gt;m\le n&lt;/math&gt; sums on the right, then you will get an overestimate if &lt;math&gt;m&lt;/math&gt; is odd and an underestimate if &lt;math&gt;m&lt;/math&gt; is even.<br /> So, <br /> <br /> &lt;math&gt; \left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|&lt;/math&gt;,<br /> <br /> &lt;math&gt; \left|\bigcup_{i=1}^n A_i\right|\ge \sum_{i=1}^n\left|A_i\right|<br /> -\sum_{i &lt; j}\left|A_i\cap A_j\right| &lt;/math&gt;,<br /> <br /> &lt;math&gt; \left|\bigcup_{i=1}^n A_i\right|\le \sum_{i=1}^n\left|A_i\right|<br /> -\sum_{i &lt; j}\left|A_i\cap A_j\right| +\sum_{i&lt;j&lt;k}\left|A_i\cap A_j\cap A_k\right| &lt;/math&gt;,<br /> <br /> and so on.<br /> <br /> == Examples ==<br /> <br /> * http://www.artofproblemsolving.com/Forum/viewtopic?t=83102<br /> * http://www.artofproblemsolving.com/Forum/viewtopic?t=61283<br /> <br /> * [http://mathideas.org/problems/2006/6/5.pdf Counting Divisors with PIE!]<br /> <br /> == See also ==<br /> <br /> * [[Combinatorics]]<br /> * [[Overcounting]]</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Bertrand%27s_Postulate&diff=5322 Bertrand's Postulate 2006-06-29T18:39:00Z <p>Fedja: </p> <hr /> <div>==Formulation==<br /> '''Bertrand's postulate''' states that for any [[positive integer]] &lt;math&gt;n&lt;/math&gt;, there is a [[prime number|prime]] between &lt;math&gt;n&lt;/math&gt; and &lt;math&gt;2n&lt;/math&gt;. Despite its name, it is in fact a theorem.<br /> ==Proof==<br /> It is similar to the proof of Chebyshev's estimates in the [[Prime Number Theorem|prime number theorem]] article but requires a closer look at the [[combinations|binomial coefficient]] &lt;math&gt;2n\choose n&lt;/math&gt;. Assuming that the reader is familiar with that proof, the Bertrand postulate can be proved as follows.<br /> <br /> Note that the power with which a prime &lt;math&gt;p&lt;/math&gt; satisfying &lt;math&gt;\frac{2n}3&lt;p\le n&lt;/math&gt; appears in the prime factorization of &lt;math&gt;2n\choose n&lt;/math&gt; is &lt;math&gt;\left\lfloor\frac{2n}{p}\right\rfloor-<br /> 2\left\lfloor\frac{n}{p}\right\rfloor=2-2=0&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\frac{2^{2n}}{(2n+1)}\le{2n\choose n}\le<br /> \left(\prod_{p\le\sqrt{2n}}p^{\lfloor\log_p (2n)\rfloor}\right)\cdot<br /> \left(\prod_{\sqrt{2n}&lt;p\le\frac{2n}3}p\right)\cdot<br /> \left(\prod_{n&lt;p\le {2n}}p\right)\,.<br /> &lt;/math&gt;<br /> <br /> The first product does not exceed &lt;math&gt;(2n)^{\sqrt{2n}}&lt;/math&gt; and the second one does not exceed &lt;math&gt;4^{\frac {2n}3}&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\left(\prod_{n&lt;p\le{2n}}p\right)\ge \frac{4^{\frac n3}}{(2n+1)(2n)^{\sqrt {2n}}}&lt;/math&gt;<br /> <br /> The right hand side is strictly greater than &lt;math&gt;1&lt;/math&gt; for &lt;math&gt;n\ge 500&lt;/math&gt;, so it remains to prove the Bertrand postulate for &lt;math&gt;n&lt;500&lt;/math&gt;. In order to do it, it suffices to present a sequence of primes starting with &lt;math&gt;2&lt;/math&gt; in which each prime does not exceed twice the previous one and the last prime is above &lt;math&gt;500&lt;/math&gt;. One such possible sequence is<br /> &lt;math&gt;2,3,5,7,13,23,43,83,163,317,631&lt;/math&gt;.<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> {{stub}}</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=User:Fedja&diff=5311 User:Fedja 2006-06-29T17:20:06Z <p>Fedja: </p> <hr /> <div>I'm going to use this page mainly as a &quot;sandbox&quot; for trying various Wiki's constructions. No personal information will be disclosed here (unless I change my mind).<br /> <br /> ==Test for [[zeta function]]==<br /> Another test for [[zeta function]] redirect<br /> <br /> &lt;table&gt;<br /> &lt;tr&gt;&lt;td&gt;&lt;math&gt;A&lt;/math&gt;&lt;/td&gt;&lt;td&gt;B&lt;/td&gt;&lt;/tr&gt;<br /> &lt;tr&gt;&lt;td&gt;C&lt;/td&gt;&lt;td&gt;&lt;math&gt;D&lt;/math&gt;&lt;/td&gt;&lt;/tr&gt;<br /> &lt;/table&gt;</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Talk:Prime_Number_Theorem&diff=5305 Talk:Prime Number Theorem 2006-06-29T17:15:08Z <p>Fedja: </p> <hr /> <div>This proof is much harder than the proof using the [[zeta function]]. To do that, you just have to show that there are no zeros on the one line. --[[User:ComplexZeta|ComplexZeta]] 12:48, 29 June 2006 (EDT)<br /> <br /> Hmmm... The fact that zeta-function has no zeroes with &lt;math&gt;\Re z=1&lt;/math&gt; will be used here for sure but it is not the end of the story: to the best of my knowledge, to finish, one has to use either Riemann's explicit formula for &lt;math&gt;\pi(x)&lt;/math&gt;, or some complex analysis trick, or some Tauberian theorem. I was inclined to use the last approach because I find it a bit more natural than the other two. But, perhaps, you know some clever shortcut I am unaware of. If so, I'll be most grateful if you write the proof you know. --[[User:Fedja|Fedja]] 13:15, 29 June 2006 (EDT)</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=Prime_Number_Theorem&diff=5274 Prime Number Theorem 2006-06-29T14:11:54Z <p>Fedja: /* Connection with Riemann zeta function */</p> <hr /> <div>{{stub}}<br /> ==Introduction==<br /> The aim of this article is to present the proof of the '''prime number theorem''' that says that the number &lt;math&gt;\pi(n)&lt;/math&gt; of [[prime]]s not exceeding &lt;math&gt;n&lt;/math&gt; is approximately &lt;math&gt;\frac n{\ln n}&lt;/math&gt; or, more precisely, that<br /> <br /> &lt;math&gt;\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.&lt;/math&gt;<br /> <br /> Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material. <br /> <br /> We shall start with some elementary observations due to Chebyshev. <br /> ==Chebyshev's estimates==<br /> The key observation is that &lt;math&gt;{2m\choose m}=\frac{(2m)!}{(m!)^2}&lt;/math&gt; is divisible by all primes &lt;math&gt;p&lt;/math&gt; satisfying &lt;math&gt;m&lt;p\le 2m&lt;/math&gt;. Indeed, every such prime appears in the numerator &lt;math&gt;(2m)!&lt;/math&gt; and does not appear in the denominator &lt;math&gt;(m!)^2&lt;/math&gt;. Thus, &lt;math&gt;\prod_{m&lt;p\le 2m}p\le {2m\choose m}\le 2^{2m}&lt;/math&gt; (from now on, &lt;math&gt;p&lt;/math&gt; will always stand for a prime number, so, to shorten the notation, we will not explicitly write &quot;&lt;math&gt;p&lt;/math&gt; is prime&quot; in the descriptions of sum and product ranges). Similarly, considering &lt;math&gt;{2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}&lt;/math&gt;, we see that <br /> &lt;math&gt;\prod_{m+1&lt;p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}&lt;/math&gt; (the last inequality holds because &lt;math&gt;{2m+1\choose m}={2m+1\choose m+1}&lt;/math&gt; and &lt;math&gt;{2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}&lt;/math&gt;). Now we are ready to prove the <br /> ===Upper bound for the product of primes===<br /> ====Lemma 1====<br /> For every positive integer &lt;math&gt;n&lt;/math&gt;, we have<br /> &lt;math&gt;\prod_{p\le n}p\le 4^n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 1====<br /> [[Induction]] on &lt;math&gt;n&lt;/math&gt;. The base &lt;math&gt;n=1&lt;/math&gt; is obvious. Suppose now that the statement holds for all numbers strictly less than &lt;math&gt;n&lt;/math&gt;. If &lt;math&gt;n=2m&lt;/math&gt; is even, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m}p\right)\cdot \left(\prod_{m&lt;p\le 2m}p\right)\le<br /> 4^m 2^{2m}=4^{2m}=4^n.<br /> &lt;/math&gt;<br /> <br /> If &lt;math&gt;n=2m+1&lt;/math&gt; is odd, then<br /> <br /> &lt;math&gt;\prod_{p\le n}p=\left(\prod_{p\le m+1}p\right)\cdot \left(\prod_{m+1&lt;p\le 2m+1}p\right)\le<br /> 4^{m+1} 2^{2m}=4^{2m+1}=4^n.<br /> &lt;/math&gt;<br /> ----<br /> From this lemma we can easily derive the <br /> ===Upper bound for the number of primes===<br /> ====Lemma 2====<br /> &lt;math&gt;\pi(n)\le 4\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 1 as &lt;math&gt;\sum_{p\le n}\ln p\le n\ln 4&lt;/math&gt;. It follows that<br /> &lt;math&gt;\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n&lt;p&lt;n}\ln p\le n\ln 4&lt;/math&gt;.<br /> But then &lt;math&gt;\pi(n)\le 2\ln 4\frac{n}{\ln n}+\pi(\sqrt n)\le 2\ln 4\,\frac{n}{\ln n}+\sqrt n&lt; 4\frac{n}{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;.<br /> ----<br /> Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. <br /> ===Lower bound for the product of primes===<br /> ====Lemma 3====<br /> &lt;math&gt;\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}&lt;/math&gt;.<br /> <br /> ====Proof of Lemma 3====<br /> The idea is again to investigate the [[prime factorization]] of <br /> &lt;math&gt;{n\choose \lfloor \frac n2 \rfloor}&lt;/math&gt;. We shall give the proof for odd &lt;math&gt;n=2m+1&lt;/math&gt; (the case of even &lt;math&gt;n&lt;/math&gt; is similar). Recall that the power in which a prime number &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;\ell!&lt;/math&gt; equals &lt;math&gt;\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots&lt;/math&gt; (see [[factorial]] for the proof).<br /> Therefore, the power in which &lt;math&gt;p&lt;/math&gt; appears in the prime factorization of &lt;math&gt;{n\choose m}&lt;/math&gt; equals &lt;math&gt;\sum_{k\ge 1}\left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac m{p^k}\right\rfloor-\left\lfloor \frac {m+1}{p^k}\right\rfloor\right)&lt;/math&gt; Note that each term in the last sum does not exceed &lt;math&gt;1&lt;/math&gt; and the number of non-zero terms does not exceed &lt;math&gt;\left\lfloor {\log_p n}\right\rfloor&lt;/math&gt;, which is &lt;math&gt;1&lt;/math&gt; for all &lt;math&gt;\sqrt n&lt;p\le n&lt;/math&gt;.<br /> Hence <br /> <br /> &lt;math&gt;{n\choose m}\le \left(\prod_{\sqrt n&lt;p\le n}p\right)\cdot\left(\prod_{p\le \sqrt n}p^{\lfloor\log_p n\rfloor}\right)\le \left(\prod_{p\le n}p\right)\cdot n^{\pi(\sqrt n)}\le n^{\sqrt n}\cdot \prod_{p\le n}p&lt;/math&gt;.<br /> <br /> On the other hand, &lt;math&gt;{n\choose m}&lt;/math&gt; is the largest of the &lt;math&gt;n+1&lt;/math&gt; binomial coefficients whose sum is &lt;math&gt;2^n&lt;/math&gt;. Thus, &lt;math&gt;{n\choose m}\ge \frac{2^n}{(n+1)}&lt;/math&gt; whence the estimate of the lemma.<br /> ===Lower bound for the number of primes===<br /> ====Lemma 4====<br /> &lt;math&gt;\pi(n)\ge \frac 12\,\frac n{\ln n}&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;<br /> <br /> ====Proof of Lemma 2====<br /> Rewrite the inequality of Lemma 3 as &lt;math&gt;\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n &gt; \frac 12 n&lt;/math&gt; for large &lt;math&gt;n&lt;/math&gt;. <br /> But the left hand side does not exceed &lt;math&gt;\pi(n)\ln n&lt;/math&gt; whence the lemma.<br /> <br /> ----<br /> We haven't proved the prime number theorem yet, but we showed that <br /> &lt;math&gt;\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}&lt;/math&gt;<br /> for all sufficiently large &lt;math&gt;n&lt;/math&gt;. For many readers it is probably a good idea to stop here and to proceed to [[Bertrand's postulate]]. The material below this point requires good knowledge of analysis and is, probably, accessible to college students only.<br /> <br /> ==Von Mangoldt function and reformulation of the prime number theorem==<br /> <br /> For a positive integer &lt;math&gt;n&lt;/math&gt;, define &lt;math&gt;\Lambda(n)=\ln p&lt;/math&gt; if &lt;math&gt;n&lt;/math&gt; is a pure positive integer power of a prime &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;\Lambda(n)=0&lt;/math&gt; otherwise (so &lt;math&gt;\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2&lt;/math&gt;, &lt;math&gt;\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3&lt;/math&gt; and so on. Let &lt;math&gt;\psi(x)=\sum_{n\le x}\Lambda(n)&lt;/math&gt; <br /> ====Lemma 5====<br /> The prime number theorem is equivalent to &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> ====Proof of Lemma 5====<br /> Note that for &lt;math&gt;x\ge 1&lt;/math&gt;, we have &lt;math&gt;\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p&lt;/math&gt;. Since &lt;math&gt;\lfloor \log_p x\rfloor\ln p\le \ln x&lt;/math&gt;, we immediately get &lt;math&gt;\psi(x)\le \pi(x)\ln x&lt;/math&gt;. Let now &lt;math&gt;\alpha&lt;1&lt;/math&gt;. For &lt;math&gt;x^\alpha&lt;p\le x&lt;/math&gt;, we have &lt;math&gt;\ln p\ge \alpha \ln x&lt;/math&gt; and, therefore, &lt;math&gt;\psi(x)\ge \sum_{x^\alpha&lt;p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x&lt;/math&gt;, which can be rewritten as &lt;math&gt;\pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> \pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;. Thus,<br /> <br /> &lt;math&gt;\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+<br /> x^\alpha\ln x&lt;/math&gt;.&lt;/math&gt; <br /> <br /> Assume now that we know that &lt;math&gt;\lim_{x\to+\infty}\frac{\psi(x)}{x}=1&lt;/math&gt;.<br /> Dividing by &lt;math&gt;x&lt;/math&gt; and passing to the limit as &lt;math&gt;x\to+\infty&lt;/math&gt;, we get<br /> <br /> &lt;math&gt;1\le\liminf_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le \limsup_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le\frac 1\alpha\,.&lt;/math&gt;<br /> <br /> Since it is true for all &lt;math&gt;\alpha&lt;1&lt;/math&gt;, we conclude that<br /> &lt;math&gt;\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1&lt;/math&gt;. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise.<br /> <br /> ==Connection with Riemann [[zeta function]]==<br /> Write &lt;math&gt;\zeta&lt;/math&gt;-function as the Euler product &lt;math&gt;\zeta(s)=\prod_p (1-p^{-s})^{-1}&lt;/math&gt; and take minus logarithmic derivative of both sides. We'll get the formula<br /> <br /> &lt;math&gt;-\frac{\zeta'(s)}{\zeta(s)}=\sum_p\frac {p^{-s}\ln p}{1-p^{-s}}=\sum_p\sum_{k\ge 1}\frac{\ln p}{p^{ks}}=\sum_{n\ge 1}\frac {\Lambda(n)}{n^s}=\int_0^\infty \frac{d\psi(x)}{x^s}<br /> =s\int_{0}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}&lt;/math&gt;<br /> <br /> valid for &lt;math&gt;\Re s&gt;1&lt;/math&gt;.<br /> <br /> <br /> ''To be continued''</div> Fedja https://artofproblemsolving.com/wiki/index.php?title=User:Fedja&diff=5273 User:Fedja 2006-06-29T14:09:30Z <p>Fedja: </p> <hr /> <div>I'm going to use this page mainly as a &quot;sandbox&quot; for trying various Wiki's constructions. No personal information will be disclosed here (unless I change my mind).<br /> <br /> ==Test for [[zeta function]]==<br /> Another test for [[zeta function]] redirect</div> Fedja