Asymptotic Improvements of Lower Bounds for the Least Common Multiples of Arithmetic Progressions

Daniel M. Kane; Scott Duke Kominers

}
//]]>
</script>
<input type="hidden" name="__VIEWSTATEGENERATOR" id="__VIEWSTATEGENERATOR" value="E39AC016" />
<script type="text/javascript">RegisterSod("sp.core.js", "\u002f_layouts\u002fsp.core.js?rev=7ByNlH\u00252BvcgRJg\u00252BRCctdC0w\u00253D\u00253D");</script><script type="text/javascript">RegisterSod("sp.res.resx", "\u002f_layouts\u002fScriptResx.ashx?culture=en\u00252Dus\u0026name=SP\u00252ERes\u0026rev=b6\u00252FcRx1a6orhAQ\u00252FcF\u00252B0ytQ\u00253D\u00253D");</script><script type="text/javascript">RegisterSod("sp.ui.dialog.js", "\u002f_layouts\u002fsp.ui.dialog.js?rev=Tpcmo1\u00252FSu6R0yewHowDl5g\u00253D\u00253D");RegisterSodDep("sp.ui.dialog.js", "sp.core.js");RegisterSodDep("sp.ui.dialog.js", "sp.res.resx");</script><script type="text/javascript">RegisterSod("core.js", "\u002f_layouts\u002f1033\u002fcore.js?rev=Emb5hNX1RZMNXk9oS82yvA\u00253D\u00253D");</script>
<script type="text/javascript">
//<![CDATA[
var _spFormDigestRefreshInterval = 1440000;window.g_updateFormDigestPageLoaded = new Date(); window.g_updateFormDigestPageLoaded.setDate(window.g_updateFormDigestPageLoaded.getDate() -5);function loadMDN2() { EnsureScript('MDN.js', typeof(loadFilterFn), null); }
function loadMDN1() { ExecuteOrDelayUntilScriptLoaded(loadMDN2, 'sp.ribbon.js'); }
_spBodyOnLoadFunctionNames.push('loadMDN1');//]]>
</script>
<script type="text/javascript">RegisterSod("sp.runtime.js", "\u002f_layouts\u002fsp.runtime.js?rev=IGffcZfunndj0247nOxKVg\u00253D\u00253D");RegisterSodDep("sp.runtime.js", "sp.core.js");RegisterSodDep("sp.runtime.js", "sp.res.resx");</script><script type="text/javascript">RegisterSod("sp.js", "\u002f_layouts\u002fsp.js?rev=\u00252B4ZEyA892P3T0504qi0paw\u00253D\u00253D");RegisterSodDep("sp.js", "sp.core.js");RegisterSodDep("sp.js", "sp.runtime.js");RegisterSodDep("sp.js", "sp.ui.dialog.js");RegisterSodDep("sp.js", "sp.res.resx");</script><script type="text/javascript">RegisterSod("cui.js", "\u002f_layouts\u002fcui.js?rev=OOyJv78CADNBeet\u00252FvTvniQ\u00253D\u00253D");</script><script type="text/javascript">RegisterSod("inplview", "\u002f_layouts\u002finplview.js?rev=WB6Gy8a027aeNCq7koVCUg\u00253D\u00253D");RegisterSodDep("inplview", "core.js");RegisterSodDep("inplview", "sp.js");</script><script type="text/javascript">RegisterSod("ribbon", "\u002f_layouts\u002fsp.ribbon.js?rev=F\u00252BUEJ66rbXzSvpf7nN69wQ\u00253D\u00253D");RegisterSodDep("ribbon", "core.js");RegisterSodDep("ribbon", "sp.core.js");RegisterSodDep("ribbon", "sp.js");RegisterSodDep("ribbon", "cui.js");RegisterSodDep("ribbon", "sp.res.resx");RegisterSodDep("ribbon", "sp.runtime.js");RegisterSodDep("ribbon", "inplview");</script><script type="text/javascript">RegisterSod("sp.ui.policy.resources.resx", "\u002f_layouts\u002fScriptResx.ashx?culture=en\u00252Dus\u0026name=SP\u00252EUI\u00252EPolicy\u00252EResources\u0026rev=YhBHGmUAGyJ3lAgSdE4V\u00252Fw\u00253D\u00253D");</script><script type="text/javascript">RegisterSod("mdn.js", "\u002f_layouts\u002fmdn.js?rev=gwmFFJ2\u00252FfFacqXWAqG\u00252FqKg\u00253D\u00253D");RegisterSodDep("mdn.js", "sp.core.js");RegisterSodDep("mdn.js", "sp.runtime.js");RegisterSodDep("mdn.js", "sp.js");RegisterSodDep("mdn.js", "cui.js");RegisterSodDep("mdn.js", "ribbon");RegisterSodDep("mdn.js", "sp.ui.policy.resources.resx");</script>
<script type="text/javascript">
//<![CDATA[

function _spNavigateHierarchyEx(nodeDiv, dataSourceId, dataPath, url, listInContext, type, additionalQString) {
    SetAdditionalNavigateHierarchyQString(additionalQString);
    g_originalSPNavigateFunc(nodeDiv, dataSourceId, dataPath, url, listInContext, type);
}

g_originalSPNavigateFunc = _spNavigateHierarchy;
_spNavigateHierarchy = _spNavigateHierarchyEx;
var _fV4UI = true;//]]>
</script>
<script type="text/javascript">RegisterSod("msstring.js", "\u002f_layouts\u002f1033\u002fmsstring.js?rev=QtiIcPH3HV7LgVSO7vONFg\u00253D\u00253D");</script><script type="text/javascript">RegisterSod("browserScript", "\u002f_layouts\u002f1033\u002fnon_ie.js?rev=EVTj1bu32\u00252FMla6SDN\u00252FsNTA\u00253D\u00253D");</script>
<script type="text/javascript">
//<![CDATA[
var __wpmExportWarning='This Web Part Page has been personalized. As a result, one or more Web Part properties may contain confidential information. Make sure the properties contain information that is safe for others to read. After exporting this Web Part, view properties in the Web Part description file (.WebPart) by using a text editor such as Microsoft Notepad.';var __wpmCloseProviderWarning='You are about to close this Web Part.  It is currently providing data to other Web Parts, and these connections will be deleted if this Web Part is closed.  To close this Web Part, click OK.  To keep this Web Part, click Cancel.';var __wpmDeleteWarning='You are about to permanently delete this Web Part.  Are you sure you want to do this?  To delete this Web Part, click OK.  To keep this Web Part, click Cancel.';//]]>
</script>
</form>

Go to main content

Article | Canadian Mathematical Bulletin

Asymptotic Improvements of Lower Bounds for the Least Common Multiples of Arithmetic Progressions

by Daniel M. Kane and Scott Duke Kominers

Abstract

For relatively prime positive integers and r, we consider the least common multiple L_n:=\mathop{\textrm{lcm}}(u_0,u_1,\dots, u_n) of the finite arithmetic progression \{u_k:=u_0+kr\}_{k=0}^n. We derive new lower bounds on L_n that improve upon those obtained previously when either u_0 or n is large. When r is prime, our best bound is sharp up to a factor of n+1 for u_0 properly chosen, and is also nearly sharp as n\to\infty.

Keywords: Mathematical Methods;

Format: Print

Find at Harvard Purchase

Citation:

Kane, Daniel M., and Scott Duke Kominers. "Asymptotic Improvements of Lower Bounds for the Least Common Multiples of Arithmetic Progressions." Canadian Mathematical Bulletin 57, no. 3 (September 2014): 551–561.

About the Author

Scott Duke Kominers

MBA Class of 1960 Associate Professor of Business Administration

Entrepreneurial Management

View Profile »
View Publications »

More from the Author

Working Paper | HBS Working Paper Series | 2019

Collusion in Brokered Markets

John William Hatfield, Scott Duke Kominers and Richard Lowery

The U.S. residential real estate agency market presents a puzzle for economic theory: commissions on real estate transactions have remained constant and high for decades even though agent entry is frequent and agents’ costs of providing service are low. We model the real estate agency market, and other brokered markets, via repeated extensive form games; in our game, brokers first post prices for customers and then choose which agents on the other side of the market to work with. We show that prices appreciably higher than the competitive prices can be sustained (for a fixed discount factor) regardless of the number of brokers; this is done through strategies that condition willingness to transact with each broker on that broker’s initial posted prices. Our results can thus rationalize why brokered markets exhibit pricing high above marginal cost despite fierce competition for customers; moreover, our model can help explain why agents and platforms who have tried to reduce commissions have had trouble entering the market.

Citation:
Hatfield, John William, Scott Duke Kominers, and Richard Lowery. "Collusion in Brokered Markets." Harvard Business School Working Paper, No. 20-023, September 2019. View Details

Cite View Details SSRN Read Now Related
Article | Operations Research Letters | September 2019

Optimizing Reserves in School Choice: A Dynamic Programming Approach

Franklyn Wang, Ravi Jagadeesan and Scott Duke Kominers

We introduce a new model of school choice with reserves in which a social planner is constrained by a limited supply of reserve seats and tries to find an optimal matching according to a social welfare function. We construct the optimal distribution of reserves via a quartic-time dynamic programming algorithm. Due to the modular nature of the dynamic program, the mechanism is strategy-proof for reserve-eligible students.

Keywords: matching; reserves; dynamic programming; Marketplace Matching; Mathematical Methods;

Citation:
Wang, Franklyn, Ravi Jagadeesan, and Scott Duke Kominers. "Optimizing Reserves in School Choice: A Dynamic Programming Approach." Operations Research Letters 47, no. 5 (September 2019): 438–446. View Details

Cite View Details Find at Harvard Read Now Related
Case | HBS Case Collection | February 2019 (Revised August 2019)

Maccabitech: The Promise of Israel's Healthcare Data

Scott Duke Kominers and Carin-Isabel Knoop

This case is set in mid-2019, when Qualcomm was struggling with unwanted takeover battles, fights with Apple and the Chinese government, and internal dissension on the board of directors. Ten years earlier Qualcomm was hailed as a monopoly on CDMA technologies and its derivatives—it appeared to be positioned to become the next dominant technology company in the tradition of Microsoft and Intel. But as the industry changed, Qualcomm’s competitive position seriously weakened. The purpose of the case is to explore central questions in strategy formulation: 1. how to build a long-term sustainable position based on technology, 2. how to design an IP strategy to lock in customers for the long run, 3. how to build a global standard and appropriate returns on that standard, and 4. how to respond when your historical business model starts to crumble.

Keywords: big data; healthcare; Data and Data Sets; Two-Sided Platforms; Health Care and Treatment; Innovation and Invention; Research; Entrepreneurship; Risk Management; Israel;

Citation:
Kominers, Scott Duke, and Carin-Isabel Knoop. "Maccabitech: The Promise of Israel's Healthcare Data." Harvard Business School Case 819-032, February 2019. (Revised August 2019.) View Details

Cite View Details Educators Purchase Related

Faculty & Research

Asymptotic Improvements of Lower Bounds for the Least Common Multiples of Arithmetic Progressions

Abstract

Citation:

About the Author

More from the Author