2025-11-10T03:13:53.693617

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions

Chang, Fang
In this paper, we uncover a new uncertainty principle that governs the complexity of Boolean functions. This principle manifests as a fundamental trade-off between two central measures of complexity: a combinatorial complexity of its supported set, captured by its Vapnik-Chervonenkis dimension ($\mathrm{VC}(f)$), and its algebraic structure, captured by its polynomial degree over various fields. We establish two primary inequalities that formalize this trade-off:$\mathrm{VC}(f)+°(f)\ge n,$ and $\mathrm{VC}(f)+°_{\mathbb{F}_2}(f)\ge n$. In particular, these results recover the classical uncertainty principle on the discrete hypercube, as well as the Sziklai--Weiner's bound in the case of $\mathbb{F}_2$.
academic

VC-Dimension vs Degree: বুলিয়ান ফাংশনের জন্য একটি অনিশ্চয়তা নীতি

মৌলিক তথ্য

  • পেপার আইডি: 2510.13705
  • শিরোনাম: VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
  • লেখক: ফ্যান চ্যাং (নানকাই বিশ্ববিদ্যালয়ের পরিসংখ্যান ও ডেটা বিজ্ঞান একাডেমি এবং কোরিয়ার মৌলিক বিজ্ঞান গবেষণা প্রতিষ্ঠান), ইজিয়া ফ্যাং (সিঙ্গাপুর জাতীয় বিশ্ববিদ্যালয়ের গণিত বিভাগ)
  • শ্রেণীবিভাগ: math.CO cs.CC cs.DM
  • প্রকাশনার সময়: ২০২৫ সালের ১৭ অক্টোবর
  • পেপার লিংক: https://arxiv.org/abs/2510.13705

সারসংক্ষেপ

এই পেপারটি বুলিয়ান ফাংশনের জটিলতা নিয়ন্ত্রণকারী একটি নতুন অনিশ্চয়তা নীতি প্রকাশ করে। এই নীতিটি দুটি মূল জটিলতা পরিমাপের মধ্যে একটি মৌলিক বিনিময় হিসাবে প্রকাশিত হয়: সমর্থন সেটের সমন্বয়গত জটিলতা (Vapnik-Chervonenkis মাত্রা VC(f) দ্বারা চিহ্নিত) এবং বীজগাণিতিক কাঠামোর জটিলতা (বিভিন্ন ক্ষেত্রে বহুপদ মাত্রা দ্বারা চিহ্নিত)। পেপারটি এই বিনিময়কে আনুষ্ঠানিক করার জন্য দুটি প্রধান অসমতা প্রতিষ্ঠা করে: VC(f) + deg(f) ≥ n এবং VC(f) + deg_F₂(f) ≥ n। এই ফলাফলগুলি বিশেষভাবে বিচ্ছিন্ন হাইপারকিউবে ক্লাসিক্যাল অনিশ্চয়তা নীতি এবং F₂ ক্ষেত্রে Sziklai-Weiner সীমানা পুনরুদ্ধার করে।

গবেষণার পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. বুলিয়ান ফাংশনের মৌলিকতা: {0,1}ⁿ বুলিয়ান হাইপারকিউবে সংজ্ঞায়িত ফাংশনগুলি সমন্বয়গত গণিত এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানের মৌলিক বস্তু ২. ফুরিয়ার সম্প্রসারণ প্রতিনিধিত্ব: প্রতিটি এই ধরনের ফাংশন f : {0,1}ⁿ → ℝ রৈখিক সমন্বয় f = Σ_{S⊆n} f̂(S)·χ_S হিসাবে প্রতিনিধিত্ব করা যায় ३. জটিলতা পরিমাপের বৈচিত্র্য: বুলিয়ান ফাংশনের জটিলতা চিহ্নিত করার একাধিক উপায় রয়েছে, যার মধ্যে রয়েছে সমন্বয়গত জটিলতা এবং বীজগাণিতিক জটিলতা

গবেষণার প্রেরণা

१. কম প্রভাব বুলিয়ান ফাংশন গবেষণা: কম প্রভাব বুলিয়ান ফাংশন গবেষণা দ্বারা অনুপ্রাণিত, সীমাবদ্ধ VC মাত্রার বুলিয়ান ফাংশনের ফুরিয়ার বর্ণালী কাঠামোগত বৈশিষ্ট্য অন্বেষণ করা २. জটিলতা পরিমাপের সম্পর্ক: VC মাত্রা (সমন্বয়গত জটিলতা) এবং বহুপদ মাত্রা (বীজগাণিতিক জটিলতা) মধ্যে মৌলিক সম্পর্ক অধ্যয়ন করা ३. তাত্ত্বিক একীকরণ: চরম সমন্বয় গণিত এবং বুলিয়ান ফাংশন বিশ্লেষণকে সংযুক্ত করার সেতু খুঁজে বের করা

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

বিদ্যমান Sauer-Perles-Shelah উপপাদ্য এবং Schwartz-Zippel উপপাদ্যের সমন্বয় শুধুমাত্র দুর্বল বিনিময় সম্পর্ক d log₂(en/d) + d* ≥ n প্রদান করতে পারে, যখন এই পেপারের ফলাফল এটিকে d + d* ≥ n এ শক্তিশালী করে।

মূল অবদান

१. নতুন অনিশ্চয়তা নীতি প্রতিষ্ঠা: বাস্তব সংখ্যার ক্ষেত্রে VC মাত্রা এবং বহুপদ মাত্রার মধ্যে মৌলিক বিনিময় সম্পর্ক প্রমাণ করা: VC(f) + deg(f) ≥ n २. সীমিত ক্ষেত্রে সম্প্রসারণ: VC মাত্রা এবং F₂ ক্ষেত্রে বহুপদ মাত্রার বিনিময় সম্পর্ক প্রমাণ করা: VC(f) + deg_F₂(f) ≥ n ३. তাত্ত্বিক ফলাফলের একীকরণ: বিচ্ছিন্ন হাইপারকিউবে ক্লাসিক্যাল অনিশ্চয়তা নীতি এবং Sziklai-Weiner সীমানা পুনরুদ্ধার করা ४. Null d-design এর সাথে সংযোগ স্থাপন: Frankl এবং Pach দ্বারা প্রবর্তিত null d-design ধারণার সাথে গভীর সংযোগ প্রকাশ করা ५. অন্যান্য জটিলতা পরিমাপে সম্প্রসারণ: VC মাত্রা এবং সিদ্ধান্ত গাছের জটিলতা, সংবেদনশীলতা, সার্টিফিকেট জটিলতা ইত্যাদি অন্যান্য বুলিয়ান ফাংশন জটিলতা পরিমাপের বিনিময় সম্পর্ক অন্বেষণ করা

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

বুলিয়ান ফাংশন f : {0,1}ⁿ → {0,1} এর VC মাত্রা VC(f) এবং এর বহুপদ মাত্রা deg(f), deg_F₂(f) এর মধ্যে পরিমাণগত সম্পর্ক অধ্যয়ন করা।

মূল উপপাদ্য

উপপাদ্য 1.2: যেকোনো অশূন্য বুলিয়ান ফাংশন f : {0,1}ⁿ → {0,1} এর জন্য, VC(f) + deg(f) ≥ n।

উপপাদ্য 1.5: যেকোনো অশূন্য বুলিয়ান ফাংশন f : {0,1}ⁿ → {0,1} এর জন্য, VC(f) + deg_F₂(f) ≥ n।

প্রমাণ কৌশল

উপপাদ্য 1.2 এর প্রমাণ পদ্ধতি

१. প্রমাণ দ্বারা বিরোধাভাস: ধরুন deg(f) ≤ n - d - 1, যেখানে d = VC(f) २. ফুরিয়ার সহগ সীমাবদ্ধতা: মাত্রা সীমাবদ্ধতা ব্যবহার করে f̂(S^c) = 0 সব |S| ≤ d এর জন্য পান ३. সমন্বয়গত শর্ত উদ্ভব: ফুরিয়ার বিশ্লেষণের মাধ্যমে #{F ∈ ℱ | F ∩ S = T} ≡ 0 (mod 2) শর্ত উদ্ভব করা ४. Null d-design সংযোগ: এই শর্তটি null d-design এর সংজ্ঞার সমতুল্য প্রমাণ করা ५. বিরোধাভাস উৎপাদন: Lemma 2.3 ব্যবহার করে প্রমাণ করা যে null d-design সন্তুষ্ট করে এমন পরিবার অবশ্যই VC মাত্রা ≥ d+1 থাকতে হবে, যা বিরোধাভাস সৃষ্টি করে

উপপাদ্য 1.5 এর প্রমাণ পদ্ধতি

१. সমন্বয়গত লেম্মা: প্রথমে Lemma 2.4 প্রমাণ করা, সমান ছেদ গণনা শর্ত এবং VC মাত্রার মধ্যে সম্পর্ক স্থাপন করা २. F₂ বহুপদ প্রতিনিধিত্ব: Proposition 2.7 ব্যবহার করে F₂ বহুপদ সহগের সূত্র প্রদান করা ३. সরাসরি নির্মাণ: নির্দিষ্ট একপদ নির্মাণের মাধ্যমে মাত্রা নিম্নসীমা প্রমাণ করা

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. Null d-design এর প্রয়োগ: Frankl-Pach এর null d-design ধারণাকে বুলিয়ান ফাংশন জটিলতা বিশ্লেষণে সৃজনশীলভাবে প্রয়োগ করা २. Möbius বিপরীতের ব্যবহার: বুলিয়ান জালিতে Möbius বিপরীত সূত্র চতুরভাবে ব্যবহার করে বিভিন্ন গণনা শর্তের সমতুল্যতা স্থাপন করা ३. একীভূত প্রমাণ কাঠামো: বাস্তব সংখ্যার ক্ষেত্র এবং F₂ ক্ষেত্রের ফলাফলের জন্য একীভূত প্রমাণ পদ্ধতি প্রদান করা

পরীক্ষামূলক সেটআপ

গণনামূলক যাচাইকরণ

পেপারটি নিম্ন মাত্রার ক্ষেত্রে সমতা সন্তুষ্ট করে এমন ফাংশনগুলি প্রোগ্রামিং এর মাধ্যমে গণনা করে যাচাই করেছে:

nমোট ফাংশন সংখ্যাdeg(f)+VC(f)=n এর ফাংশন সংখ্যাdeg_F₂(f)+VC(f)=n এর ফাংশন সংখ্যা
1433
216911
32565583
4655366332491

কোড উপলব্ধতা

সম্পর্কিত গণনা কোড GitHub এ প্রকাশ্যে উপলব্ধ: https://github.com/FangYijia/deg-VC

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল যাচাইকরণ

१. সমতা ক্ষেত্রের জটিলতা: গণনা ফলাফল দেখায় যে সমতা সন্তুষ্ট করার ক্ষেত্রগুলি অত্যন্ত জটিল, শুধুমাত্র সাব-কিউবে সীমাবদ্ধ নয় २. নির্দিষ্ট পাল্টা উদাহরণ: n=4 এর সময় deg(f)=VC(f)=2 কিন্তু সমর্থন সেট সাব-কিউব নয় এমন নির্দিষ্ট ফাংশন উদাহরণ প্রদান করা ३. বৈশিষ্ট্য নির্ধারণের কঠিনতা: সমতা সন্তুষ্ট করার শর্তের সম্পূর্ণ বৈশিষ্ট্য নির্ধারণ অত্যন্ত কঠিন কাজ

তাত্ত্বিক প্রয়োগ

१. ক্লাসিক্যাল ফলাফল পুনরুদ্ধার: বুলিয়ান ফাংশনের ক্লাসিক্যাল অনিশ্চয়তা নীতি সফলভাবে পুনরুদ্ধার করা (Corollary 1.6) २. Sziklai-Weiner সীমানা: F₂ ক্ষেত্রে ওজন সীমাবদ্ধ বহুপদের Sziklai-Weiner নিম্নসীমা পুনরুদ্ধার করা (Corollary 1.7)

সম্পর্কিত কাজ

মূল সম্পর্কিত গবেষণা

१. Sauer-Perles-Shelah উপপাদ্য: VC মাত্রা এবং সেট পরিবারের আকারের মধ্যে ক্লাসিক্যাল সম্পর্ক প্রদান করে २. Schwartz-Zippel লেম্মা: বহুপদের অশূন্য বিন্দু সংখ্যার নিম্নসীমা প্রদান করে ३. Frankl-Pach এর null d-design: এই পেপারের প্রমাণের মূল সরঞ্জাম প্রদান করে ४. বুলিয়ান ফাংশন বিশ্লেষণ: ফুরিয়ার বিশ্লেষণ, সংবেদনশীলতা অনুমান ইত্যাদি ক্লাসিক্যাল তত্ত্বের সাথে সংযোগ

এই পেপারের অনন্য অবদান

বিদ্যমান কাজের তুলনায়, এই পেপারটি প্রথমবারের মতো VC মাত্রা এবং বহুপদ মাত্রার মধ্যে কঠোর বিনিময় সম্পর্ক প্রতিষ্ঠা করে এবং একীভূত তাত্ত্বিক কাঠামো প্রদান করে।

সিদ্ধান্ত এবং আলোচনা

প্রধান সিদ্ধান্ত

१. বুলিয়ান ফাংশন জটিলতার নতুন অনিশ্চয়তা নীতি প্রতিষ্ঠা করা: VC(f) + deg(f) ≥ n এবং VC(f) + deg_F₂(f) ≥ n २. এই অসমতাগুলি কঠোর, সাব-কিউব নির্দেশক ফাংশন সমতা অর্জন করে ३. একাধিক ক্লাসিক্যাল ফলাফল পুনরুদ্ধার এবং একীভূত করা

সম্প্রসারণ দিকনির্দেশনা

१. বুলিয়ান স্লাইস: বুলিয়ান হাইপারকিউব স্লাইসে অনুরূপ বিনিময় সম্পর্ক অন্বেষণ করা २. সাধারণ আবেলীয় গ্রুপ: যেকোনো সীমিত আবেলীয় গ্রুপে সাধারণীকরণ অধ্যয়ন করা ३. অন্যান্য জটিলতা পরিমাপ: সিদ্ধান্ত গাছের জটিলতা, সংবেদনশীলতা, সার্টিফিকেট জটিলতার সাথে সম্পর্ক

সীমাবদ্ধতা

१. সমতা বৈশিষ্ট্য নির্ধারণ: সমতা সন্তুষ্ট করার শর্তের সম্পূর্ণ বৈশিষ্ট্য নির্ধারণ এখনও কঠিন २. গণনামূলক জটিলতা: উচ্চ মাত্রার ক্ষেত্রে গণনামূলক যাচাইকরণ অসম্ভব হয়ে ওঠে ३. সাধারণীকরণ সীমাবদ্ধতা: কিছু সাধারণীকরণ (যেমন সংবেদনশীলতার সাথে সম্পর্ক) পাল্টা উদাহরণ রয়েছে

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক গভীরতা: সমন্বয়গত জটিলতা এবং বীজগাণিতিক জটিলতার মধ্যে গভীর সংযোগ প্রতিষ্ঠা করা २. প্রযুক্তিগত উদ্ভাবন: null d-design ইত্যাদি উন্নত প্রযুক্তির চতুর প্রয়োগ ३. ফলাফল একীকরণ: একীভূত কাঠামোতে একাধিক ক্লাসিক্যাল ফলাফল পুনরুদ্ধার করা ४. প্রমাণ কমনীয়তা: সংক্ষিপ্ত এবং গভীর প্রমাণ পদ্ধতি প্রদান করা

অপূর্ণতা

१. সমতা বৈশিষ্ট্য নির্ধারণ অসম্পূর্ণ: সমতা সন্তুষ্ট করার শর্তের বৈশিষ্ট্য নির্ধারণ এখনও অপর্যাপ্ত २. কিছু সাধারণীকরণের সীমাবদ্ধতা: যেমন সংবেদনশীলতার সাথে সম্পর্কের সাধারণীকরণে পাল্টা উদাহরণ রয়েছে ३. গণনামূলক যাচাইকরণের পরিসীমা: শুধুমাত্র নিম্ন মাত্রার ক্ষেত্রে সম্পূর্ণ যাচাইকরণ সম্ভব

প্রভাব

१. তাত্ত্বিক অবদান: বুলিয়ান ফাংশন জটিলতা তত্ত্বের জন্য নতুন মৌলিক সরঞ্জাম প্রদান করা २. পদ্ধতিগত মূল্য: null d-design এর প্রয়োগ সম্পর্কিত গবেষণার জন্য নতুন চিন্তাভাবনা প্রদান করা ३. সংযোগ সেতু: চরম সমন্বয় গণিত এবং বুলিয়ান ফাংশন বিশ্লেষণের মধ্যে নতুন সংযোগ স্থাপন করা

প্রয়োগযোগ্য পরিস্থিতি

१. তাত্ত্বিক কম্পিউটার বিজ্ঞান: জটিলতা তত্ত্ব, শেখার তত্ত্বে প্রয়োগ २. চরম সমন্বয় গণিত: সেট পরিবারের কাঠামোগত বৈশিষ্ট্য গবেষণা ३. বুলিয়ান ফাংশন বিশ্লেষণ: ফুরিয়ার বিশ্লেষণ, প্রভাব বিশ্লেষণ ইত্যাদি ক্ষেত্র

সংদর্ভ

পেপারটি ৩৩টি গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যা বুলিয়ান ফাংশন বিশ্লেষণ, চরম সমন্বয় গণিত, জটিলতা তত্ত্ব ইত্যাদি একাধিক ক্ষেত্রের ক্লাসিক্যাল এবং অগ্রগামী কাজ অন্তর্ভুক্ত করে, যা গবেষণার জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।

সারসংক্ষেপ: এটি বুলিয়ান ফাংশন জটিলতা তত্ত্বে গুরুত্বপূর্ণ অবদান রাখে এমন একটি পেপার, যা VC মাত্রা এবং বহুপদ মাত্রার মধ্যে মৌলিক বিনিময় সম্পর্ক প্রতিষ্ঠা করে এবং বুলিয়ান ফাংশনের অন্তর্নিহিত জটিলতা বোঝার জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে।