{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/15597"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/15597","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Bijective proofs of partition identities and covering systems","abstract":"This dissertation involves two topics. The first is on the theory of partitions, which is discussed in Chapters 2 − 5. The second is on covering systems, which are considered in Chapters 6 − 8. In 2000, Farkas and Kra used their theory of theta functions to establish a beautiful theorem on colored partitions, and they asked for a bijective proof of it. In Chapter 2, we give a bijective proof of a more general partition identity, with the Farkas and Kra partition theorem being a special case. We then derive three further general partition identities and give bijective proofs of these as well. The quintuple product identity is one of the most famous and useful identities in the theory of theta functions and q-series, and dates back to 1916 or earlier. In his recent survey paper on this identity, Shaun Cooper remarked that there does not exist a bijective proof of it. In Chapter 3, employing bijective proofs of Jacobi’s triple product identity and Euler’s pentagonal number theorem, we provide the first bijective proof of the quintuple product identity. In a recent paper, The parity in partition identities, George Andrews investigated parity questions in partition identities and listed 15 open problems at the end of his paper. In Chapter 4, we provide solutions to the first two open problems suggested by Andrews. More precisely, we provide combinatorial proofs of two partition identities which were derived by comparing Andrews’ new identity with G¨ollnitz-Gordon identities or certain generalizations thereof. In our last chapter on partitions, Chapter 5, we give a combinatorial proof of a companion to Euler’s famous recurrence formula for the sum of divisors function. Euler’s recurrence formula had previously been combinatorially proved using a double counting argument, but its equally famous companion has not heretofore been established combinatorially. We not only provide such a combinatorial proof, but we also give a combinatorial proof of a vast generalization as well. M. Filaseta, K. Ford, S. Konyagin, C. Pomerance and G. Yu proved that if the least modulus N of a covering system is sufficiently large, then the sum of reciprocals of the moduli is bounded below by a function of N, tending to infinity as N goes to infinity, which confirms a conjecture of P. Erd˝os and J. L. Selfridge. They also showed that, forK > 1, the complement in Z of any union of residue classes r(n) (mod n) with distinct n from (N,KN] has density at least dK for N sufficiently large, which implies a conjecture of P. Erd˝os and R. L. Graham. In Chapter 6, we first define covering systems in number fields, and extend those results to arbitrary number fields. In Chapter 7, we give an explicit version of their first theorem to provide a specific number for the least modulus of a covering system, where the reciprocal sum is strictly bigger than 1. In the last chapter, Chapter 8, we consider exact covering systems in number fields. Motivated by the theorem of Davenport, Mirsky, Newman and Rado that there does not exist an exact covering system with distinct moduli, we raise the question whether or not this is true for covering systems in algebraic number fields. We provide affirmative answers for certain quadratic fields.","abstract_html":"This dissertation involves two topics. The first is on the theory of partitions, which is discussed in Chapters 2 − 5. The second is on covering systems, which are considered in Chapters 6 − 8. In 2000, Farkas and Kra used their theory of theta functions to establish a beautiful theorem on colored partitions, and they asked for a bijective proof of it. In Chapter 2, we give a bijective proof of a more general partition identity, with the Farkas and Kra partition theorem being a special case. We then derive three further general partition identities and give bijective proofs of these as well. The quintuple product identity is one of the most famous and useful identities in the theory of theta functions and q-series, and dates back to 1916 or earlier. In his recent survey paper on this identity, Shaun Cooper remarked that there does not exist a bijective proof of it. In Chapter 3, employing bijective proofs of Jacobi’s triple product identity and Euler’s pentagonal number theorem, we provide the first bijective proof of the quintuple product identity. In a recent paper, The parity in partition identities, George Andrews investigated parity questions in partition identities and listed 15 open problems at the end of his paper. In Chapter 4, we provide solutions to the first two open problems suggested by Andrews. More precisely, we provide combinatorial proofs of two partition identities which were derived by comparing Andrews’ new identity with G¨ollnitz-Gordon identities or certain generalizations thereof. In our last chapter on partitions, Chapter 5, we give a combinatorial proof of a companion to Euler’s famous recurrence formula for the sum of divisors function. Euler’s recurrence formula had previously been combinatorially proved using a double counting argument, but its equally famous companion has not heretofore been established combinatorially. We not only provide such a combinatorial proof, but we also give a combinatorial proof of a vast generalization as well. M. Filaseta, K. Ford, S. Konyagin, C. Pomerance and G. Yu proved that if the least modulus N of a covering system is sufficiently large, then the sum of reciprocals of the moduli is bounded below by a function of N, tending to infinity as N goes to infinity, which confirms a conjecture of P. Erd˝os and J. L. Selfridge. They also showed that, forK > 1, the complement in Z of any union of residue classes r(n) (mod n) with distinct n from (N,KN] has density at least dK for N sufficiently large, which implies a conjecture of P. Erd˝os and R. L. Graham. In Chapter 6, we first define covering systems in number fields, and extend those results to arbitrary number fields. In Chapter 7, we give an explicit version of their first theorem to provide a specific number for the least modulus of a covering system, where the reciprocal sum is strictly bigger than 1. In the last chapter, Chapter 8, we consider exact covering systems in number fields. Motivated by the theorem of Davenport, Mirsky, Newman and Rado that there does not exist an exact covering system with distinct moduli, we raise the question whether or not this is true for covering systems in algebraic number fields. We provide affirmative answers for certain quadratic fields.","abstract_has_math":false,"creators":["Kim, Sun"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Berndt, Bruce C.","Ford, Kevin","Hildebrand, A.J.","Duursma, Iwan M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-05-14T20:51:58Z","date_published":"2010-05-14T20:51:58Z","updated_at":"2026-07-22T22:25:08Z","subjects":["partitions","bijective proofs","covering systems"],"languages":["en"],"rights":["Copyright 2010 Sun Kim"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/15597","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Berndt, Bruce C.","Ford, Kevin","Hildebrand, A.J.","Duursma, Iwan M."]},{"key":"dc:creator","label":"Author","values":["Kim, Sun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-05-14T20:51:58Z","2012-05-15T10:00:50Z","2010-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["partitions","bijective proofs","covering systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Sun Kim"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/15597"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This dissertation involves two topics. The first is on the theory of partitions, which is discussed in Chapters 2 − 5. The second is on covering systems, which are considered in Chapters 6 − 8. In 2000, Farkas and Kra used their theory of theta functions to establish a beautiful theorem on colored partitions, and they asked for a bijective proof of it. In Chapter 2, we give a bijective proof of a more general partition identity, with the Farkas and Kra partition theorem being a special case. We then derive three further general partition identities and give bijective proofs of these as well. The quintuple product identity is one of the most famous and useful identities in the theory of theta functions and q-series, and dates back to 1916 or earlier. In his recent survey paper on this identity, Shaun Cooper remarked that there does not exist a bijective proof of it. In Chapter 3, employing bijective proofs of Jacobi’s triple product identity and Euler’s pentagonal number theorem, we provide the first bijective proof of the quintuple product identity. In a recent paper, The parity in partition identities, George Andrews investigated parity questions in partition identities and listed 15 open problems at the end of his paper. In Chapter 4, we provide solutions to the first two open problems suggested by Andrews. More precisely, we provide combinatorial proofs of two partition identities which were derived by comparing Andrews’ new identity with G¨ollnitz-Gordon identities or certain generalizations thereof. In our last chapter on partitions, Chapter 5, we give a combinatorial proof of a companion to Euler’s famous recurrence formula for the sum of divisors function. Euler’s recurrence formula had previously been combinatorially proved using a double counting argument, but its equally famous companion has not heretofore been established combinatorially. We not only provide such a combinatorial proof, but we also give a combinatorial proof of a vast generalization as well. M. Filaseta, K. Ford, S. Konyagin, C. Pomerance and G. Yu proved that if the least modulus N of a covering system is sufficiently large, then the sum of reciprocals of the moduli is bounded below by a function of N, tending to infinity as N goes to infinity, which confirms a conjecture of P. Erd˝os and J. L. Selfridge. They also showed that, forK > 1, the complement in Z of any union of residue classes r(n) (mod n) with distinct n from (N,KN] has density at least dK for N sufficiently large, which implies a conjecture of P. Erd˝os and R. L. Graham. In Chapter 6, we first define covering systems in number fields, and extend those results to arbitrary number fields. In Chapter 7, we give an explicit version of their first theorem to provide a specific number for the least modulus of a covering system, where the reciprocal sum is strictly bigger than 1. In the last chapter, Chapter 8, we consider exact covering systems in number fields. Motivated by the theorem of Davenport, Mirsky, Newman and Rado that there does not exist an exact covering system with distinct moduli, we raise the question whether or not this is true for covering systems in algebraic number fields. We provide affirmative answers for certain quadratic fields.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-04-16T15:03:00Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5)","Made available in DSpace on 2010-05-14T20:51:58Z (GMT). No. of bitstreams: 3 Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5) 1_Kim_Sun.pdf: 942332 bytes, checksum: 90e23ed3281c9ca7c7d86db57dbfaf65 (MD5) license.txt: 4056 bytes, checksum: a6e1370a8a6b177b1cbcfef7530939f1 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2010-05-14T20:52:50Z Item is restricted until 2012-05-14T20:52:43Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-05-15T10:00:50Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Mathematics (ID: 749) No. of bitstreams: 4 1_Kim_Sun.pdf.txt: 190382 bytes, checksum: b0efbd0ca8ef569f69c10fac4ba15e64 (MD5) Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5) 1_Kim_Sun.pdf: 942332 bytes, checksum: 90e23ed3281c9ca7c7d86db57dbfaf65 (MD5) license.txt: 4056 bytes, checksum: a6e1370a8a6b177b1cbcfef7530939f1 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-05-15T10:00:50Z"]},{"key":"dc:title","label":"Title","values":["Bijective proofs of partition identities and covering systems"]}]}],"canonical_facts":{"dc:contributor":["Berndt, Bruce C.","Ford, Kevin","Hildebrand, A.J.","Duursma, Iwan M."],"dc:creator":["Kim, Sun"],"dc:date":["2010-05-14T20:51:58Z","2012-05-15T10:00:50Z","2010-05"],"dc:description":["This dissertation involves two topics. The first is on the theory of partitions, which is discussed in Chapters 2 − 5. The second is on covering systems, which are considered in Chapters 6 − 8. In 2000, Farkas and Kra used their theory of theta functions to establish a beautiful theorem on colored partitions, and they asked for a bijective proof of it. In Chapter 2, we give a bijective proof of a more general partition identity, with the Farkas and Kra partition theorem being a special case. We then derive three further general partition identities and give bijective proofs of these as well. The quintuple product identity is one of the most famous and useful identities in the theory of theta functions and q-series, and dates back to 1916 or earlier. In his recent survey paper on this identity, Shaun Cooper remarked that there does not exist a bijective proof of it. In Chapter 3, employing bijective proofs of Jacobi’s triple product identity and Euler’s pentagonal number theorem, we provide the first bijective proof of the quintuple product identity. In a recent paper, The parity in partition identities, George Andrews investigated parity questions in partition identities and listed 15 open problems at the end of his paper. In Chapter 4, we provide solutions to the first two open problems suggested by Andrews. More precisely, we provide combinatorial proofs of two partition identities which were derived by comparing Andrews’ new identity with G¨ollnitz-Gordon identities or certain generalizations thereof. In our last chapter on partitions, Chapter 5, we give a combinatorial proof of a companion to Euler’s famous recurrence formula for the sum of divisors function. Euler’s recurrence formula had previously been combinatorially proved using a double counting argument, but its equally famous companion has not heretofore been established combinatorially. We not only provide such a combinatorial proof, but we also give a combinatorial proof of a vast generalization as well. M. Filaseta, K. Ford, S. Konyagin, C. Pomerance and G. Yu proved that if the least modulus N of a covering system is sufficiently large, then the sum of reciprocals of the moduli is bounded below by a function of N, tending to infinity as N goes to infinity, which confirms a conjecture of P. Erd˝os and J. L. Selfridge. They also showed that, forK > 1, the complement in Z of any union of residue classes r(n) (mod n) with distinct n from (N,KN] has density at least dK for N sufficiently large, which implies a conjecture of P. Erd˝os and R. L. Graham. In Chapter 6, we first define covering systems in number fields, and extend those results to arbitrary number fields. In Chapter 7, we give an explicit version of their first theorem to provide a specific number for the least modulus of a covering system, where the reciprocal sum is strictly bigger than 1. In the last chapter, Chapter 8, we consider exact covering systems in number fields. Motivated by the theorem of Davenport, Mirsky, Newman and Rado that there does not exist an exact covering system with distinct moduli, we raise the question whether or not this is true for covering systems in algebraic number fields. We provide affirmative answers for certain quadratic fields.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-04-16T15:03:00Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5)","Made available in DSpace on 2010-05-14T20:51:58Z (GMT). No. of bitstreams: 3 Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5) 1_Kim_Sun.pdf: 942332 bytes, checksum: 90e23ed3281c9ca7c7d86db57dbfaf65 (MD5) license.txt: 4056 bytes, checksum: a6e1370a8a6b177b1cbcfef7530939f1 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2010-05-14T20:52:50Z Item is restricted until 2012-05-14T20:52:43Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-05-15T10:00:50Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Mathematics (ID: 749) No. of bitstreams: 4 1_Kim_Sun.pdf.txt: 190382 bytes, checksum: b0efbd0ca8ef569f69c10fac4ba15e64 (MD5) Kim_Sun.pdf: 942340 bytes, checksum: be169f6f30ab211d0ff34f9b814c5825 (MD5) 1_Kim_Sun.pdf: 942332 bytes, checksum: 90e23ed3281c9ca7c7d86db57dbfaf65 (MD5) license.txt: 4056 bytes, checksum: a6e1370a8a6b177b1cbcfef7530939f1 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-05-15T10:00:50Z"],"dc:identifier":["http://hdl.handle.net/2142/15597"],"dc:language":["en"],"dc:rights":["Copyright 2010 Sun Kim"],"dc:subject":["partitions","bijective proofs","covering systems"],"dc:title":["Bijective proofs of partition identities and covering systems"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:08Z"}