Manuel Sartori

RESTRICTION AND EXHAUSTION IN ARABIC EVALUATION OF THE RELEVANCE OF THE INFLECTIONAL DECLENSION

Keywords: desinential inflection, grammatical rationalism, iʿrāb, relevance, Sībawayhi

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

نا َ ت ْ جئ َ أ ْ وا ُ ال َ ق َ ر َ ذ َ ن َ و ُ ه َ د ْ ح َ و َ هللا َ د ُ ب ْ ع َ ن ِ ل ا َ ن ُ آؤ َ اب َ ء ُ د ُ ب ْ ع َ ي َ ان َ ك ا َ م (1)
qālū a-jiʾtanā li-naʿbuda llāha waḥdahu wa-nadhara mā kāna yaʿbudu ābāʾunā (Q. 7, 70)

They said, "Why, hast you come to us that we may serve God alone, and forsake that our fathers served?" 4

(2

) ا ً ور ُ ف ُ ن ْ م ِ ه ِ ر ٰ ـ َ ب ْ د َ أ ی َ ل َ ع ْ ا ْ و َّ ل َ و ُ ه َ د ْ ح َ و ِ ان َ ء ْ ر ُ ق ْ آل ي ِ ف َ ك َّ ب َ ر َ ت ْ ر َ ك َ ذ ا َ ذ ِ إ َ و
wa-idhā dhakarta rabbaka fī l-qurʾāni waḥdahu wallaw ʿalā adbārihim nufūran (Q. 17, 46)

And when thou mentionest thy Lord only in the Qurʾān, they turn in their traces in aversion. 5

(3

) ِ ة َ ر ِ خ َ ْ آْل ِ ب َ ون ُ ن ِ م ْ ؤ ُ ي َ َل َ ين ِ ذ َّ آل ُ وب ُ ل ُ ق ْ ت َّ ز َ أ َ م ْ آش ُ ه َ د ْ ح َ و ُ هللا َ ر ِ ك ُ ذ ا َ ذ ِ إ َ و
wa-idhā dhukira llāhu waḥdahu ishmaʾazzat qulūbu lladhīna lā yuʾminūna bi-l-ākhirati (Q. 39, 45)

When God is mentioned alone, then shudder the hearts of those who believe not in the Hereafter. 6 Nāfiʿ (d. 169/785) transmitted by Warsh (d. 197/812), in use in the Maghreb (cf. Qurʾān(2)).

No divergence of reading is reported concerning these six verses by Dānī (d. 444/1052-1053) in his Taysīr (cf. Dānī, Taysīr, respectively 357, 411, 498, 499, 501 and 531), or by Maḥallī (d. 864/1459) and Suyūṭī (d. 911/1505) in their Tafsīr al-Jalālayn al-muyassar (cf. Maḥallī and Suyūṭī, Jalālayn, respectively 159, 286, 463, 468, 476 et 549).

Arberry, The Koran, I, 180, compare to "[Son peuple] répliqua: 'Es-tu venu à nous afin que nous adorions Allah, en son unicité, et que nous délaissions ce qu'adoraient nos pères?'" (Blachère, Le Coran, 184).

Arberry, The Koran, I, 307, compare to "Quand tu évoques ton Seigneur, l'Unique, dans la Prédication, ils tournent le dos par répulsion" (Blachère, Le Coran, 310).

https://archive.org/stream/QuranAJArberry/Quran-A%20J%20Arberry_djvu.txt (accessed on 24/01/2021), compare to "Quand Allah, en Son unicité, est mentionné, les coeurs de ceux qui ne croient point en la [Vie] dernière se hérissent" (Blachère, Le Coran, 493).

(4) ْ م ُ ت ْ ر َ ف َ ك ُ ه َ د ْ ح َ و ُ هللا َ ي ِ ع ُ د ا َ ذ ِ إ ُ ه َّ ن َ أ ِ
ب كم ِ ٰل ٰ َ ذ dhālikum bi-annahu idhā duʿiya llāhu waḥdahu kafartum (Q. 40, 12) That is because, when God was called to alone, you disbelieved. 7 (5)

َ ن َ س ْ أ َ ب ْ ا ْ و َ أ َ ر ا َّ م َ ل َ ف ا َ ين ِ ك ِ ر ْ ش ُ م ِ ه ِ ب ا َّ ن ُ ك ا َ م ِ ب ا َ ن ْ ر َ ف َ ك َ و ُ ه َ د ْ ح َ و ِ اهلل ِ ب ا َّ ن َ ام َ ء ْ وا ُ ال َ ق
fa-lammā raʾaw baʾsanā qālū āmannā bi-llāhi waḥdahu wa-kafarnā bi-mā kunnā bihi mushrikīna (Q. 40, 84) Then, when they saw Our might, they said, "We believe in God alone, and we disbelieve in that we were associating with Him." 8

(6) ُ ه َ د ْ ح َ و ِ اهلل ِ ب ْ وا ُ ن ِ م ْ ؤ ُ ت ی َّ ت َ ح ا ً د َ ب َ أ ُ آء َ ض ْ غ َ ب ْ آل َ و ُ ة َ و ٰ َ د َ ع ْ آل ُ م ُ ك َ ن ْ ي َ ب َ و ا َ ن َ ن ْ ي َ ب ا َ د َ ب َ و
wa-badā baynanā wa-baynakumu l-ʿadāwatu wa-l-baghḍāʾu abadan ḥattā tuʾminū bi-llāhi waḥdahu (Q. 60, 4) And between us and you enmity has shown itself, and hatred for ever, until you believe in God alone. 9

There is apparent inflectional agreement in (1) and ( 2) where in both cases, the waḥdahu.

Should we consider that it is also invariable in (1) and ( 2) and that the inflectional agreement is only apparent? Daniel Reig (1929-2007), in his Arabic-French dictionary, seems to suggest this, since he invariably indicates waḥdaka/ki/hu/hā. 10 However, he mentions the existence of an expression, nasīj waḥdihi "unique of his kind," where waḥdihi, within an annexation (iḍāfa), is the adnominal complement/second term of annexation (muḍāf ilayhi) of the noun nasīj which is the first (muḍāf).

The waḥdihi" wa-"ʿuyayr(V) waḥdihi" wa-"juḥaysh(V) waḥdihi"). 13 This implies that waḥdahu is invariably in the accusative and only very exceptionally in other cases, in particular the genitive, when wahḍ is the second term of an annexation. The "problem" is that if we turn to Hans Bodo Gerhardt Wehr's (1905-1981) dictionary, we find the following expressions li-waḥdihi ("to oneself, for oneself only") and ʿalā waḥdihi (same meaning as nasīj waḥdihi) 14 where the expression is by no means invariable, even when it is not the second term of an annexation. There, waḥdihi takes on its expected grammatical 10 Cf. Reig, Dictionnaire, art. 5866 W-Ḥ-D. 11 Cf. Gottschalk, Abū ʿUbayd al-Ḳāsim b. Sallām.

12 V notes the possible inflectional vowel.

13 Azharī, Tahdhīb, V, 199a-b. See also Lane, An Arabic-English Lexicon, VIII, 2927b-c. inflection after a preposition that requires the genitive case.

To complicate matters, before Reig and Wehr, Albin de Kazimirski Biberstein (1808-1887) also cites the usage of the nominative in the following examples: Allāh waḥduhu "Dieu un, unique" ("One God, only [one]"), huwa waḥduhu "Lui seul" ("Only him"), lahu waḥduhu15 "À lui seul" ("To him only"), hum waḥduhum "Eux seuls" ("Them alone"). He adds raʾaytuhu waḥdahu, where the accusative seems to be derived from the agreement between waḥd and its antecedent, -hu, which itself is positionally in the accusative, but also jalasa waḥdahu and jalasa ʿalā waḥdihi "il était assis tout seul" ("he was sitting all alone"). Whereas the latter example seems correct from a declensional point of view, this is not true of the former. He gives two other examples of inflectional agreement: jalasā ʿalā waḥdayhimā "ils étaient assis deux tous seuls, en tête à tête" ("they were both sitting alone, face to face") and jalasū ʿalā waḥdihim "ils étaient assis seuls" ("they were sitting alone") where waḥd, within prepositional phrases, is indeed in the genitive case. Finally, he gives the three exceptional expressions encountered in Azharī:

On dit : huwa nasīju waḥdihi Il est seul, il fait bande à part (se dit avec éloge).

-ʿuyayru waḥdihi Petit chameau qui va tout seul, ou juḥayshu waḥdihi Anon qui va tout seul (se dit d'un homme têtu et bête). On dit aussi : rujaylu waḥdihi C'est un homme singulier. 16 This suggests that the final expression noted by Kazimirski should be included in addition to the other three if we consider ʿuyayr and juḥaysh to be two separate expressions, which is not necessary, or as the third exceptional expression alongside nasīj waḥdihi and juḥaysh/ʿuyayr waḥdihi based on the assumption that these two expressions are interchangeable. 17 This expression is also found in its non-diminutive form, namely rajul waḥdihi. 18 In any case, we would therefore have waḥdahu as well as waḥduhu and waḥdihi, which is far removed from the peremptory assertions of Abū ʿUbayd and Anbārī reported by Azharī who state that there are only three exceptions in the accusative to this expression, and that these three exceptions are only in the genitive. Finally, as shown below, this is not an issue of language evolution that would have been recorded by Kazimirski or Wehr, since Sībawayhi (d. 180/796?) himself records the three case ending possibilities alongside the invariable accusative ending.

Waḥdahu: an uninflected noun phrase

According to Abū Bakr b. Anbārī quoted by Azharī, three explanations can be advanced to explain why waḥdahu is in the accusative: the fact that for the socalled Baṣra school it is a circumstantial qualifier (ḥāl), the fact that waḥdahu has qāla wa-fī naṣb "waḥdahu" thalāthat aqwāl qāla jamāʿa min al-Baṣriyyīn 17 The edition of Tahdhīb al-lugha, when placing ʿuyayr waḥdihi in square brackets after juḥaysh waḥdihi, indicates that these two expressions should be seen as equivalent and interchangeable. However, this is not the case in Ibn Manẓūr's (d. 711/1311) Lisān al-ʿArab who clearly distinguishes between the two expressions (cf. Ibn Manẓūr, Lisān, XV, 166a).

Note that most of what Ibn Manẓūr says comes entirely from Azharī.

huwa manṣūb ʿalā al-ḥāl wa-qāla Yūnus "waḥdahu" huwa bi-manzilat "ʿindahu" wa-qāla Hishām "waḥdahu" huwa manṣūb ʿalā al-maṣdar. 20 Abū ʿUbayd only gives two explanations for the fact that waḥd is uninflected in the accusative: the arguments by the proponents of the school of Baṣra where he says it is a verbal noun; and proponents (including himself) of the argument that waḥd is the adjective (ṣifa) of the substantive to which it is associated:

إنما أصحابنا وقال وحده تحود أي املصدر مذهب علی وحده نصبوا إنما البصريون وقال قال الصفة مذهب علی النصب .
qāla wa-qāla al-Baṣriyyūn inna-mā naṣabū "waḥdahu" ʿalā madhhab almaṣdar ay "tawaḥḥada waḥdahu" wa-qāla aṣḥābunā inna-mā al-naṣb ʿalā madhhab al-ṣifa. 21 In Yūnus' explanation, waḥda is the equivalent of ʿinda and thus a place adverbial (ẓarf makān), which Régis Blachère's (1900-1973)

translations of the examples

(1) and (3) render fairly well by "en son unicité" ("in his uniqueness").

If we accept Hishām's explanation and some of the grammarians of Baṣra, waḥda would be a verbal noun (maṣdar). This is also the position of the author of Kitāb al-ʿAyn, al-Khalīl b. Aḥmad al-Farāhīdī (d. 160/776 or 170/786 or 175/791). 22 Sībawayhi indeed reports the opinion of his master and, in the chapter hādhā bāb mā juʿila min al-asmāʾ maṣdaran ("The chapter of names considered as verbal nouns"), 23 he refers to the accusative as the first explanation and does 20 Azharī, Tahdhīb, V, 199a.

21 Azharī, Tahdhīb, V, 199b. See also Lane, An Arabic-English Lexicon, VIII, 2927b-c. not comment any further on the examples he quotes, and in particular does not explicitly provide their vocalization (bi-l-naṣb, etc.); namely marartu bihi waḥdøhø, marartu bihim waḥdøhøm and marartu bi-rajulin waḥdøhø, but the editors, Hartwig Derenbourg (1844-1908) as well as ʿAbd al-Salām Muḥammad Hārūn (1909-1988), 24 vocalize them by anticipation in the accusative (and because it is the only case that Sībawayhi just mentioned), respectively waḥdahu, waḥdahum and waḥdahu. Sībawayhi specifies that waḥdahu is similar to what is found in the language of the people of Hejaz; namely, marartu bihim thalāthatahum wa-arbaʿatahum (cf. translation infra, wa-mithl dhālika fī lughat ahl al-Ḥijāz: marartu bihim thalāthatahum wa-arbaʿatahum wa-ka-dhālika ilā al-ʿashara), 25 and then indicates, through his master Khalīl, that it is in the accusative:

الخليل وزعم ] رحمه هللا [ أنه إذا كما هؤَلء أجاوز لم فقط بهؤَلء مررت يقول فكأنه ثالثتهم نصب أجاوزه لم فقط به مررت يريد فإنما وحده قال إذا أنه .
wa-zaʿama al-Khalīl [raḥimahu Allāh]26 annahu idhā naṣaba "thalāthatahum" fa-ka-annahu yaqūlu "marartu bi-hāʾulāʾi fa-qaṭ lam ujāwiz hāʾulāʾi" ka-mā annahu idhā qāla "waḥdahu" fa-inna-mā yurīdu "marartu bihi fa-qaṭ lam ujāwizhu." 27 Khalīl, [may Allah grant him mercy,] claimed that when he puts thalāthatahum in the accusative it is as though he said: "I passed by those only, and I did not exceed those [go beyond those]", just as when he says waḥdahu he wants to say: "I only passed by him, and I did not exceed him." term ism al-maṣdar (cf. Larcher, Syntaxe, 45-46). 24 The same applies to two non-scientific editions of the Kitāb, the Būlāq edition (cf. Sībawayhi, Kitāb(2), I, 187), and that of Imīl Badīʿ Yaʿqūb (cf. Sībawayhi, Kitāb(4), I, 442). 25 Sībawayhi, Kitāb(3), I, 373. This accusative, for Sībawayhi as for Khalīl, is obviously for a verbal noun since the paraphrase 28 he gives is afradtuhum ifrādan "I singled them out one by one." 29 The same is true of Rummānī (d. 384/994) who writes: واختصصته وحده بمروري أفردته معنی علی فينتصب وحده به مررت وتقول ثم وحده بمروري الوجه هذا في التوحيد معنی فيه إذ غيره دون به اَلختصاص ي يقتض وحده ْلن الفعل هذا تحذف .

wa-taqūlu "marartu bihi waḥdahu" fa-yantanṣibu ʿalā maʿnā "afradtuhu bimurūrī waḥdahu" wa-"ikhtaṣaṣtuhu bi-murūrī waḥdahu" thumma taḥdhifu hādhā al-fiʿl li-anna "waḥdahu" yaqtaḍī al-ikhtiṣāṣ bihi dūna ghayrihi idh fīhi maʿnā al-tawḥīd fī hādhā al-wajh. 30 You say "I passed by him, him alone" and it is put in the accusative with the sense of "I reserved my passage to him, him alone" and "I especially gratified him, him alone, with my visit," then you elide this verb since "him alone" implies the fact that he, to the exclusion of any other, is concerned, meaning singling out.

The interpretation of marartu bihim thalāthatahum here is as "I passed by them, these three [only]", "just the three of them" in the sense that I have singled out these three and distinguished them from all the others by my visit which does not go beyond the case of these three. This may thus be the use of an effected object (mafʿūl muṭlaq) 31 with the elision of the verb whose meaning is "to be really alone" or "to be all alone." 32 In 28 This is a tamthīl; for more details see the article by Ayoub, which incidentally quotes the expert from the Kitāb (cf. Ayoub, De ce qui "ne se dit pas," 9-10). 29 Sībawayhi, Kitāb(3), I, 374. 30 Sībawayhi, Kitāb(3), I, 373, footnote 4. 31 Badawi et al. translate this as the "absolute object" (cf. Badawi et al., Modern Written Arabic, 169), but "effected object" seems to be a better translation, since it has affinities with the "complément résultatif" in French which better translates mafʿūl muṭlaq (cf. Larcher, Syntaxe, 45). addition to the translations which are included in Kazimirski, this is indicated by the paraphrase afradtuhum ifrādan "I singled them out one by one" mentioned by Sībawayhi as well as Abū ʿUbayd, quoted by Azharī. Abū ʿUbayd paraphrases this as tawaḥḥada waḥdahu where waḥdahu, from the same root of tawaḥḥada, is the mafʿūl muṭlaq of the latter like kalām which is from the same root of takallama in the expression takallama kalāman: thus waḥdahu is here an ism almaṣdar, a noun which, without being formally a maṣdar or the maṣdar of the relevant verb, can be used as such. 33 There is indeed a verb waḥida and a verb waḥuda, one of whose verbal nouns (maṣdar) is waḥd which has the meaning of "to be alone, unique, singular." 34 From this intransitive verb of form I, we naturally derive a transitive verb of form II waḥḥadahā which then represents the factitive of the first, with the meaning "to make into one, to make alone," that is to say "to unify, merge, make unique."

From the latter we just as naturally derive an intransitive verb of form V tawaḥḥada which is then the direct reflexive of II with the meaning "to make oneself alone," that is to say, "to isolate oneself, to be lonely."

The effected object is the basis of the adverb category in Arabic. 35 This reading applies to examples (5) and ( 6) in their French translation where it would be interpreted as amannā bi-llāhi [īmānan] waḥdan and ḥattā tuʾminū bi-llāhi

[īmānan] waḥdan, that is, "we believe in Allah by a unique belief" and "until you believe in Allah with a unique belief." In this case, the verbal noun in the position of the effected object, īmān, is elided and only its qualifier, waḥdan, remains. The latter is not strictly speaking an adjective, but rather a non-derived or primitive 33 Cf. Larcher, Syntaxe, 45-46. 34 Cf. Kazimirski, Dictionnaire, II, 1497, cf. also "waḥida fulān yawḥadu; that is, he was left alone and we say waḥida and waḥuda," waḥida fulān yawḥadu ay baqiya waḥdahu wa-yuqālu waḥida wa-waḥuda, Ibn Manẓūr, Lisān, XV, 165. Wehr adds waḥada-yaḥidu (cf. Wehr, Dictionary, 1236a). noun (ism jāmid) interpreted as a derived noun (muʾawwal bi-mushtaqq) which takes on the role of an adjective as in anta rajulun ʿadlun "you are a righteous man." 36 The other possible reading is as follows: āmannā bi-llāhi [alladhī tawaḥḥada] waḥdan "we believe in Allah who made himself truly unique" and ḥattā tuʾminū bi-llāhi [alladhī tawaḥḥada] waḥdan "until you believe in Allah who made himself truly unique." In this case, waḥdan is indeed the verbal noun in the position of the effected object. In both cases, waḥdan in the accusative becomes waḥdahu, still in the accusative and where the nunation (tanwīn) disappears because of the suffixation of the pronoun -hu whose antecedent is īmān in one case, and Allāh in the other (īmānan waḥdan > īmāna llāhi waḥdahu and Allāh alladhī tawaḥḥada waḥdan > Allāh alladhī tawaḥḥada waḥdahu).

Finally, other proponents of the Baṣra school view it as a circumstantial qualifier (ḥāl). In the case of examples ( 2) and ( 4), this would be what Blachère renders by "l'Unique" ("the Unique"); as in "alors qu'il est unique, en étant unique" ("whereas he is unique, by being unique").

Waḥd's triptosy

The fact that others (aṣḥābunā, see above) consider it also to be a qualifier (ṣifa) allows us to consider that it behaves as such, and that it agrees in inflection with its substantive. This would make it possible to have jāʾa al-rajulu waḥduhu, raʾaytu al-rajula waḥdahu and marartu bi-l-rajuli waḥdihi.

wa-ammā Banū Tamīm fa-yujrūnahu ʿalā al-ism al-awwal in kāna jarran fajarran wa-in kāna naṣban fa-naṣban wa-in kāna rafʿan fa-rafʿan. 37

As to Banū Tamīm, they make it agree with the first noun: if it is in the genitive then it is also, if it is in the accusative then it is also, if it is in the nominative then it is also.

In this case, waḥd is not strictly speaking an adjective but a non-derived or primitive noun interpreted as a derived one (see above). However, it should be considered exactly as ʿayn, nafs, kull, ʿāmma, jamīʿ or ajmaʿ; i.e., as a semantic corroborative (tawkīd maʿnawī), 38 where its meaning would be "him alone," exactly like ʿaynhu means "himself" and kullhum "all of them, them all."

According to Sībawayhi, this is exactly what Khalīl suggests: أحدا منهم أدع لم أي كلهم بهم مررت كقولك يعموا أن يريدون فكأنهم يجرونه الذين أن الخليل وزعم .

wa-zaʿama al-Khalīl anna lladhīna yujrūnahu 39 fa-ka-annahum yurīdūna an yaʿummū ka-qawlika "marartu bihim kullihim" ay lam adaʿ minhum aḥadan. 40 Khalīl claimed that those who make it agree with [what precedes it] actually want to generalize, as when one says "I passed by them, them all;" that is, I did not omit any of them.

In this case, examples (1) and (2) are transparent, since waḥdahu is the adjective of Allāha/rabbaka which is itself in the accusative. The other Qurʾānic examples where the antecedent is not in the accusative but where waḥda is, can be analyzed in several ways: as an effected object, as in the case of jalasa waḥdahu given by Kazimirski which is understood as jalasa [wa-tawaḥḥada] waḥdahu "he was 38 Cf. Ghalāyīnī, Jāmiʿ, III, 176. 39 The interpretations put forward by ʿAbd al-Salām Hārūn (and Imīl Badīʿ Yaʿqūb) seem better than Derenbourg (and therefore Būlāq) who suggest yajurrūna "they put in the genitive" (cf.

Sībawayhi, Kitāb(1), I, 157; Sībawayhi, Kitāb(2), I, 187), which is too reductive since the text clearly states the three possible inflections, including the nominative in the dialect of the Banū Tamīm.

sitting [and was isolated] all alone," as a circumstantial qualifier understood as "he was sitting in a state of isolation," or as a place adverbial, understood as "in his uniqueness."

A difference in meaning based on inflectional endings?

Sībawayhi, who bases his reasoning on Khalīl, suggests that the difference in meaning between invariability in the accusative or full inflection of the noun phrase {waḥd-+ suffixed pronoun}, is as follows:

اد اَلنفر معنی أردت إذا نصبا خمستهم يكون أيضا فكذلك التفرد معنی من هو إنما وحده وكذلك ذ كان كما جررت أحدا منهم تدع لم أنك أردت فإن قضهم في لك .

wa-ka-dhālika "waḥdahu" inna-mā huwa min maʿnā al-tafarrud fa-kadhālika ayḍan yakūnu "khamsatahum" naṣban idhā aradta maʿnā al-infirād fa-in aradta annaka lam tadaʿ minhum aḥadan jararta ka-mā kāna dhālika fī "qaḍḍahum." 41

Similarly, waḥdahu has a very strong sense of individuation, and likewise, khamsatahum is in the accusative when it means isolation. So if the intended meaning is that no one has been omitted, the genitive applies, as was the case for qaḍḍahum. 42 The invariable accusative would therefore indicate singularizing, as indicated by the theoretical or underlying paraphrase (tamthīl) expressed as afradtuhu(m) ifrādan "to single him/them out one by one," but also to restrict it solely to the elements in the set, which the other paraphrase indicates in the form of lam 41 Sībawayhi,Kitāb(3),I,375. 42 qaḍḍihim if the term is declined. In the example that Sībawayhi gives above: marartu bihim qaḍḍahum bi-qaḍīḍihim "I passed near them, them all," the expression qaḍḍahum biqaḍīḍihim does indeed mean kullhum, jamīʿhum, ajmaʿhum etc. that is, all without exception, young and old (ṣaghīrhum wa-kabīrhum). I am grateful to Issam Chehadat for this confirmation.

ujāwizhu(m) "not to [go past] exceed him/them." Thus, marartu bihi(m) waḥdahu(m) "I passed by him/them, him/them alone [no more]" would mean afradtuhu(m) bi-murūrī ifrādan wa-lam ujāwizhu(m) "I have totally individualized him/them [ him/them alone] with my visit and have not gone beyond him/them [as the object of this action = I have not seen anyone else than him/them]". Likewise, marartu bihim khamsatahum "I passed by them, these five [no more]/just the five of them" would then mean afradtuhum bi-murūrī ifrādan wa-lam ujāwizhum "I have totally individualized them [these five] by my visit and have not gone beyond them [that is, I have not seen anyone else than these five/I have seen these five and no more]". We would therefore be dealing with a double definition: in intension by the definition of the set (bihi, bihim), and in extension by the enumeration of the elements of the set (waḥdahu(m) "him/them alone," khamsatahum "these five"), where the accusative would mark a restriction, by corroboration, to the elements of the set to the exclusion of any other elements than those defined in extension ("him and him alone, them and them no others, these five and no more").

On the other hand, the full inflectional agreement would indicate not omitting any element of the set defined in intension, which the paraphrase gives as lam adaʿ minhum aḥadan "I did not omit any of them." Thus, marartu bihim khamsatihim "I passed by them, these five [no less]" would mean marartu bihim kullihim ay lam adaʿ minhum aḥadan "I passed by them, all of them, that is to say, I have not omitted any of them." The same expression in the singular, marartu bihi waḥdihi would then mean "I passed by him, him alone." Here in addition to the same double definition in intension (of the set) and in extension (of the elements of the set), the full inflectional agreement would mark an exhaustion; that is, the fact of completely exhausting the elements defined in extension. 43 Although Sībawayhi advances these various arguments with caution by using the verb zaʿama "to claim" 44 when it comes to reporting his master's opinion on the question, this semantic distinction, based solely on the desinential inflection, remains specious and questionable. Several arguments point in this direction. The first is that the distinction is first and foremost geographic, and refers to Hejaz on the one hand, and Najd on the other with the Banū Tamīm. This suffices to show that this semantic distinction should be questioned above all because "Hejaz" could actually refer, for Sībawayhi, to these 6 uninflected in a occurrences, and hence only to the language of the Qurʾān. 45 Thus, the distinction made by Sībawayhi would not be made between two living variants, but between a variant of this type, the language of the Banū Tamīm, and another, which is only scriptural (or that of a reader), which therefore does not allow for a real comparison, or at best cannot guarantee the results of such a comparison.

Regardless of the accuracy of Larcher's intuition, and besides the fact that, above all, we then face a geographic distinction, the opposition as Sībawayhi puts it between restriction and exhaustion is too ideal not to attract critical attention and identify a grammatical rationalism at work on his part: his presentation would amount to saying that for the people of the Hejaz, one would only ascertain one meaning, that of the restriction to the individuals of a set by the exclusion of all others, while, on the other hand, for the center of the Arabian Peninsula one would only understand the exhaustion of all the individuals of a set without omitting any 44 The verb zaʿama indicates that the reported fact which is considered as possibly being true as false (huwa al-qawl yakūnu ḥaqqan wa-yakūnu bāṭilan, Ibn Manẓūr, Lisān, VII, 33), even if it may have the meaning of "certifying, attesting" (wa-qad takūnu zaʿama hā-hunā bi-mʿanā shahida, Ibn Manẓūr, Lisān, VII, 34). This verb can be translated in English as "to maintain, allege, claim, pretend, declare" (cf. Wehr, Dictionary, 438b) and in French as "parler, dire quelque chose, énoncer une opinion (vraie ou fausse, un fait sûr ou douteux), croire que…, penser que…, s'emploie le plus souvent quand on rapporte les paroles des autres sans vouloir en garantir la vérité" (Kazimirski, Dictionnaire, I, 992). of them.

But there is more. Beyond the specious nature of this opposition, Sībawayhi doubtless unconsciously undermines or, at least violates the theory of a relevant desinential inflection so dear to the Arabic grammatical tradition. Indeed, if the inflection is really relevant, we must be able to distinguish, within a same linguistic variant, between several meanings. This is at least what Zajjājī (d. 337/949) wants us to believe when he relates an anecdote involving the grammarian Abū al-Aswad al-Duʾalī (d. ca. 69/688) and his daughter: the latter said to her father mā ashaddu al-ḥarri ("what is the most intense heat?") when in fact she wanted to say mā ashadda al-ḥarra ("what intense heat!"). 46 Through this anecdote, itself too perfect to be believed without critical hindsight, Zajjājī aims to show that the desinential inflection is relevant: in a given linguistic variant, the inflectional variation is the bearer of a semantic variation (interrogation vs. exclamation). 47 Ultimately, even if everything tends to qualify or even question this anecdote, the argument may seem acceptable: there are two ways of pronouncing which distinguish, within the same variant, two meanings. However, the difference in meaning is here between different geographic uses (Hejaz vs. Najd) and as a consequence between different variants: the inflectional ending is not contrastive, since the two meanings are in a complementary, not a contrastive, distribution, where the complementarity is defined by association with two 46 Cf. Zajjājī, Īḍāḥ, 89. 47 This, however, is a too perfect example to prove the relevance of desinential inflection not to itself being subject to caution. Application of the rules of orthoepy indeed leads to mā ashaddu al-ḥar vs. mā ashadda al-ḥar, such that the distinction is only based on the single short vowel, whereas the suprasegmental would make the distinction without inflection (cf. Larcher, Une relecture, 59-60) which would distinguish between mā ashadd al-ḥar (with rising intonation, which is indicative of the interrogation) and mā ashadd al-ḥar (falling intonation) without any final vowel. different linguistic variants. Some people say this with restriction in mind, others say that with exhaustion in mind. At best, it would simply be two ways of saying 48 or seeing the world and applying the inflection endings to the words, but not being able to distinguish, on the basis of this inflection, different meanings within the same variant. 49 This leads to the following conclusion. First of all, a grammarian like Sībawayhi is not fully consistent on this point with the theory he presents: 50 the relevance of iʿrāb presupposes that it plays a discriminating role within the same 48 It is exactly the same and ultimately no more or less than the use of naʿt by the so-called Kūfa school and of ṣifa by the so-called Baṣra school… 49 This is particularly true for tonal languages, such as Chinese, where it is precisely the tone, even when subtle, that makes it possible to differentiate, within the same linguistic variant, between several meanings: thus 美 (měi, "beautiful") is a parophone (or quasi-homophone) of 没 (méi, "do not") and 梅 (méi, "plum") which, on their own, are perfect homophones, pronounced exactly the same way, including the tone. In the geographic case described by Sībawayhi, it is as though we used the expressions l'accusé sera déferré au tribunal "the accused will be unchained in court" and l'accusé sera déféré au tribunal "the accused will be brought to court" where the first is pronounced [defɛre] (déf(ai/ê/è)ré) and the second [defere] and where the meaning, although very close, is not exactly the same, since the original meaning is that once the chained accused has arrived in court, the shackles are removed (attested use, since 1289 "libérer un prisonnier" ("to free a prisoner" (Jacquemard Gielée, Renart le Nouvel, éd. H. Roussel. 1717))), cf. https://www.cnrtl.fr/definition/déferré, accessed on 25/01/2021), the second meaning that he is being brought to justice. 50 The same goes for Ibn al-Ḥājib (d. 646/1249) who, while explaining why the imperative of qatala-yaqtulu is uqtul and not aqtul, specifies that the latter would have been confused with muḍāriʿ of the verb, understood as aqtul, which therefore presupposes, for there to be confusion, that Ibn al-Ḥājib knew that one does not pronounce aqtulu with the final modal vowel, but quite simply aqtul, by introducing a pause (waqf). Since, he does not presuppose that this rule was created by his grammarian predecessors, he acknowledges the fact that the grammatical aqtulu has in fact never been pronounced otherwise than aqtul. On this question, cf. Sartori, Croyant pas pratiquant, 507-511. linguistic variant, not between different linguistic variants. Sībawayhi, however, describes this variation as being linked to distinct linguistic variants. The second is that when considering this variation as an inflectional phenomenon, he sets out to find a semantic explanation: from a contemporary perspective, it is likely that once Sībawayhi defined the Tamīmi vs. Hejazi usages in inflectional terms, he was thereupon forced to attribute a semantic difference to each. This contrasts with other phenomena, such as taltala, or pronouncing the initial of a verb conjugated in muḍārīʿ by vocalizing it in i rather than in a: there, Sībawayhi never says, for example, that a verb like yifʿalu marked by the taltala, does not have the same meaning as its counterpart yafʿalu without taltala.

It thus appears that this semantic distinction seems more to be the result of a-posteriori grammatical theorizing: faced with two realizations without any real difference in meaning, and somehow trapped in what would become the Arab grammarians' own game, grammatical rationalism seeks to distinguish them, even if it means forcing distinctions which may not exist. 51 This can be viewed as a farfetched distinction, as I first did. However, as Jonathan Owens kindly suggested to me, we can also see this differently, namely from a human and professional point of view. Sībawayhi was given his datasets. Even if, as in today's dialectology and sociolinguistics, he allowed the variation to be accounted for in non-contrastive terms (imāla, taltala for instance), for a case like this, he may simply have not done the same because of the status of iʿrāb as the theoretical linchpin. He then felt he had to ascribe differences that were in fact not necessarily semantically contrastive. His treatment of waḥdshows that Sībawayhi was thinking like any good linguist would do when confronted with this type of 51 This is exactly what is at stake regarding the entirely grammatical distinction between sa-and sawfa (future markers) which is not a linguistic distinction (cf. Sartori, Construction d'une idée). In the present case it would be the equivalent of trying to grammatically explain the difference in pronunciation of the word "année" ("year") ([ane] and [ãne], especially in southwest France) by a difference in meaning when in fact it is solely about pronunciation. variation and, on a post-hoc basis, tried to work out a system behind the variation. 52 In so doing, Sībawayhi looks more like a typical linguist struggling with recalcitrant variationist data. While, as Carter has frequently observed, 53 Sībawayhi was a descriptivist, the current case suggests that this is not true all the time in the Kitāb. Sībawayhi the grammarian was also enamored of exhaustive explanations, which, as in this case, could lead to overly speculative rationalizations. This is a case where grammatical rationalism was at times detached from any linguistic reality and where the efforts at justification won out over reality itself. 54 The sacrosanct desinential inflection is once again presented as an 'open sesame' to explanation or justification, but the only conclusion it is actually possible to draw is that the Tamīmi variant did have case form, while, in the Qurʾān, the declension is not always present. 55 52 Jullien de Pommerol and Owens attempted explain the appearance or non-appearance of the imperfect prefix b-in Chadian Arabic and that of Maiduguri, Nigeria. Both spent a great deal of time analyzing these phenomena in contrastive terms (cf. Jullien de Pommerol, Grammaire pratique and Owens, Neighborhood and Ancestry, 65-65), but ultimately, no real difference emerged as confirmed to me by Jonathan Owens himself (personal communication 05/02/2021). The variation comes about through dialect mixing, not different developments in grammaticalization. 53 Cf. for example Carter, Sībawayhi and Modern Linguistics, 24 and Carter Sībawayhi's Principles, 187. 54 Cf. Suleiman, The Arabic grammatical tradition. 55 One can go even further and say that the West language; i.e., the Qurʾān, was to a certain extent, devoid of declensional inflection (cf. Vollers, Volkssprache und Schriftsprache, 22), something that the idghām al-kabīr (cf. Owens, Idghām al-Kabīr) tends to prove, as well as the existence of rhymes in the caseless reading of the Qurʾānic text (cf. for instance Larcher, Une "rime cachée"). However, this does not necessarily imply that the final vowel phenomenon of the Tamīm speaking, representative of the Eastern Peninsula, is a declination.

Conclusion

This is what can be said concerning the possible declension or not of the noun phrase waḥdahu. However, we still need to decide which translation best suits the sentence in French that launched a thousand ships. In the absence of a verb for which li-l-jīli al-shābb would be the subject, it seems difficult to make waḥdahu an effected object. It also seems difficult to make it into a place adverbial, as the context does not indicate that "speaking French" is good "inside" young people.

If the choice of translation into Arabic were to focus on waḥdahu, it would be considered a circumstantial qualifier, and interpreted as "good for young people as the only ones for whom it is good," "for whom it is good because of their young age."

That said, inflectional agreement by considering this noun phrase an apposition to al-jīli al-shābb seems better. This apposition would then be considered a corroborative: li-l-jīli al-shābb waḥdih ("for the young generation,

[it] only"). This possibility does not seem to have to be rejected on the sole grounds that the Qurʾān does not provide an example.

Finally, the fact that some apply full inflectional agreement while others consider it as uninflected, where each has its own, albeit close, but distinct meaning, is not enough to prove the relevance of the inflection: in fact, its relevance cannot be established outside the framework of a single linguistic variant and not, as is the case here, within two distinct linguistic and geographic variants. This again shows the extent to which the inflectional phenomenon in Arabic should be viewed with caution, 56 by always keeping the question in mind of whether it is a myth or a reality for that language. [START_REF] Cf | Case and Mood Endings as well as Sartori, Inflectional Endings and Sartori, Croyant pas pratiquant for various examples where this iʿrāb is not respected. Qurʾān(1) = al-Qurʾān bi-riwāyat Ḥafṣ ʿan Nāfiʿ[END_REF] MANUEL SARTORI (AIX-MARSEILLE UNIVERSITÉ, CNRS, IEP, IREMAM, AIX-EN-PROVENCE, FRANCE)

  lexicographer Abū Manṣūr Muḥammad b. Aḥmad b. al-Azhar al-Azharī (d. 370/980) writes in his Tahdhīb al-lugha that there are indeed only three exceptions to the invariability of waḥdahu. He cites Abū Bakr b. Anbārī [Muḥammad b. al-Qāsim b. Muḥammad b. Bashshār] (d. 328/940) and Abū ʿUbayd [al-Qāsim b. Sallām b. ʿAbd Allāh] (d. 224/838) 11 (respectively qāla Abū Bakr b. al-Anbārī "waḥdahu" manṣūb fī jamīʿ kalām al-ʿArab illā fī thalāthat mawāḍiʿ and qāla [Abū ʿUbayd] wa-l-ʿArab tanṣibu "waḥdahu" fī al-kalām kullihi wa-lā tarfaʿuhu wa-lā takhfiḍuhu illā fī thalāthat aḥruf "nasīj(V) 12

  the same status as ʿindahu according to Yūnus [b. Ḥabīb] (d. 182/798), 19 and finally the fact that it is a verbal noun (maṣdar) according to Hishām [b. ʿAmmār b. Nuṣayr b. Maysara b. Abān al-Silmī??] (d. 245/859): جما قال أقوال ثالثة وحده نصب وفي قال يونس وقال الحال علی منصوب هو البصريين من عة املصدر علی منصوب هو هشام وقال عنده لة بمنز هو وحده .

22

  Cf. Farāhīdī, ʿAyn, IV, 350-351. Quoted by Azharī who considered that al-Layth b. al-Muẓaffar (d. 187/803 or 190/805) was the author. For this reason, other medieval scholars preferred to say ṣāḥib Kitāb al-ʿAyn "the author of Kitāb al-ʿAyn" without further precision (cf. Sellheim, al-Layth b. al-Muẓaffar and Carter, A Twelfth, 81).

For

  more on this subject see what Quṭrub (m. 206/821) thought (cf. Versteegh, A Dissenting

Grammarian

  and Molina Rueda, El iʿrāb).

56

  Cf. Sartori, La flexion désinentielle for the details of the criticism of the relevance of the inflectional declension (iʿrāb) in Arabic, and for instance Ambros, Funktionalität, Corriente, On the Functional Yield, Corriente, Again on the Functional Yield, Dévényi, Mujāwara, Gruntfest, From the History, Larcher, Arabe Préislamique, Larcher, Épigraphie et linguistique, Larcher, Moyen arabe, Molina Rueda, El iʿrāb, Owens, Case and Proto-Arabic

  The triptosy is indeed what both Kazimirski and Wehr show (see above), but likewise what Sībawayhi explicitly says when he specifies that:

	فرفعا رفعا كان وإن فنصبا نصبا كان وإن .	ا فجر	ا جر كان إن اْلول اَلسم علی فيجرونه تميم بنو وأما

Here, we would have expected lahu waḥdihi since the suffixed pronoun of lahu is positionally in the genitive.

Kazimirski, Dictionnaire, II, 1497.

Cf. Ibn Manẓūr, Lisān, XV, 166a.

This segment is present in Hārūn's edition but not in Derenbourg.

Sībawayhi, Kitāb(3), I, 374.

Cf. Ghalāyīnī, Jāmiʿ, III, 170.

Sībawayhi, Kitāb(3), I, 374.

Sībawayhi, Kitāb(3), I, 374.


A Earls
email: aearls@bcamath.org

M C Calderer

M Desroches

A Zarnescu

S Rodrigues
email: srodrigues@bcamath.org

A phenomenological model for interfacial water near hydrophilic polymers

Keywords:

We propose a minimalist phenomenological model for the "interfacial water" phenomenon that occurs near hydrophilic polymeric surfaces. We achieve this by combining a Ginzburg-Landau approach with Maxwell's equations which leads us to a well-posed model providing a macroscopic interpretation of experimental observations. From the derived governing equations, we estimate the unknown parameters using experimental measurements from the literature. The resulting profiles of the polarization and electric potential show exponential decay near the surface, in qualitative agreement with experiments. Furthermore, the model's quantitative prediction of the electric potential at the hydrophilic surface is in excellent agreement with experiments. The proposed model is a first step towards a more complete parsimonious macroscopic model that will, for example, help to elucidate the effects of interfacial water on cells (e.g. neuronal excitability), the effects of infrared neural stimulation or the effects of drugs mediated by interfacial water.

Introduction

Water is an ubiquitous material and intrinsically associated with life. Its anomalous behavior is recognized as the origin of various phenomena in chemistry and biology. One such anomalous behavior occurs when liquid water interacts with hydrophilic polymeric surfaces (e.g. cellular membranes). These are interfaces of polymeric materials which have high affinity with water. At a microscopic scale it has been seen that the hydrophilic surface affects the electric polarization of water layers. However the mechanism for generating this polarization, based on the deformation of water molecules, is not well understood. The current paper only aims to provide a phenomenological description of this phenomenon.

Near the hydrophilic surfaces a specific phase of water was observed. This is called "interfacial water" and has emergent physical-chemical properties (different from usual liquid state of water), such as, non-zero electrical potential, reacts to light [START_REF] Chai | Effect of radiant energy on near-surface water[END_REF] and repels materials (e.g. solutes [START_REF] Zheng | Effect of buffers on aqueous soluteexclusion zones around ion-exchange resins[END_REF]). The width of the interfacial layer varies, but can range from hundreds of microns to several millimeters [START_REF] Jian Ming Zheng | Surfaces and interfacial water: Evidence that hydrophilic surfaces have long-range impact[END_REF][START_REF] Florea | Long-range repulsion of colloids driven by ion exchange and diffusiophoresis[END_REF]. The interfacial layer is typically negatively charged (but there are exceptions [START_REF] Chai | Unexpected presence of solute-free zones at metal-water interfaces[END_REF]), and the electric potential at the hydrophilic surface is negative. The layer causes charge separation in the fluid, creating a "nano-battery", and therefore it may have an important role in biology [START_REF] Ball | Water as an active constituent in cell biology[END_REF][START_REF] Chaplin | Water: its importance to life[END_REF]. However, despite the accumulation of a vast body of experimental evidence and theoretical approaches, the exact mechanisms that causes the emergence of interfacial layer is still being debated. As yet there is no macroscopic, well-posed mathematical model able to describe and predict properties of the interfacial layer. A first step is proposed in the present work.

The proposed explanations for the formation of the interfacial layer include diffusiophoresis and ion exchange [START_REF] Schurr | Phenomena associated with gel-water interfaces. analyses and alternatives to the long-range ordered water hypothesis[END_REF][START_REF] Florea | Long-range repulsion of colloids driven by ion exchange and diffusiophoresis[END_REF][START_REF] Esplandiu | Electrophoretic origin of long-range repulsion of colloids near water/nafion interfaces[END_REF], repulsive van der Waals forces [START_REF] Daniel | Exclusion zone phenomena in water-a critical review of experimental findings and theories[END_REF], or a new phase of water which is fundamentally different than the bulk one [START_REF] Gerald | The Fourth Phase of Water: Beyond Solid, Liquid, and Vapor[END_REF].

In this paper, we aim to produce a minimalistic mathematical model that predicts the interfacial water phenomenon but does not assume any particular physical mechanism is responsible for the interfacial layer formation. In section 2, we present the derivation of the model. As a first approach, we neglect ionic charges and take the unknowns of the problem to be the polarization p and the electric potential Φ. For simplicity, we will consider a one-dimensional region of water, 0 < z < M , with a hydrophilic surface located at z = 0.

To obtain the governing equations for the system, we focus on the long-time regime in which the system is stationary, postulate an energy density E(p, p , Φ ) and apply a variational method. Several parameters in the energy density E are phenomenological and must be estimated. In section 3, we first study a simplified system with an infinite domain (M = +∞) and constant relative permittivity throughout the interfacial region. In this scenario the Euler-Lagrange equations admit an exact solution, and we use experimental measurements from the literature to reverse engineer and estimate the necessary quantities.

With these parameter estimates in hand, in section 4 we then study the problem on a finite domain, M < ∞. We also allow the relative permittivity to vary throughout the interfacial region by writing it as a function of z, the distance from the hydrophilic surface. In each scenario, we find that the polarization and potential profiles have qualitatively the same shape. Also, both approaches give excellent estimates of the electric potential at the surface.

Modeling framework

In this section, we define the energy and pose the Euler-Lagrange (EL) equations on both domain types.

Far away from the hydrophilic surface, the water should be in its usual nonpolar phase:

p(z = M ) = 0 C m -2 , Φ (z = M ) = 0 V m -1 .
(

) 1
At the surface, the water should be polarized:

p(z = 0 ) = p 0 . (2)
We will also assume

Φ(M ) = 0 V. ( 3
)
The electric displacement is defined as D = ε 0 ε(z)E + p, so the electric energy density is expressed as

E elec = -D dE = - 1 2 ε 0 ε(z)(Φ ) 2 + pΦ . (4)
We also define a double-well Ginzburg-Landau potential for the polarization, with potential wells of depth quantified by the constant δ:

E GL (p) = p 2 2δ 2 (p -ap 0 ) 2 . ( 5
)
The energy density E GL encodes the fact that the fluid has two preferred states: nonpolar (p = 0), or polarized (p = ap 0 ). The constant a is one of the phenomenological parameters to be determined. The states p = 0 and p = ap 0 represent the bulk water phase and the interfacial phase, respectively. The solution we seek will exhibit a transition between these two states.

We then model the solution (p, Φ) as a critical point of the following energy functional:

E[p, Φ] = M 0 E(p, p , Φ ) dz, (6)
E(p, p , Φ ) = 1 2 κ(p ) 2 + E GL (p) + E elec (p, Φ ). ( 7
)
The three terms of the energy density E model the spatial variations of p, the phase transition, and the interaction between p and Φ, respectively. We seek a critical point (p, Φ) of ( 7) that satisfies the boundary conditions (1) and (3).

Hence, applying the principle of least action to the energy (7) yields the EL equations

∂E ∂p - ∂E ∂p = 0, (8)
∂E ∂Φ - ∂E ∂Φ = 0. ( 9
)
Equation ( 9) is Poisson's equation, which reduces to

(ε 0 ε(z)Φ ) = p , (10)
and can be integrated to give

Φ = p ε 0 ε(z) . (11)
Equation ( 8) can then be written

κp = p 1 δ 2 (p -ap 0 )(2p -ap 0 ) + 1 ε 0 ε(z) . ( 12
)
Note that p = 0 is an equilibrium point of ( 12), corresponding to the nonpolar water state. In the next two sections, we will solve ( 11) and ( 12), subject to the boundary conditions ( 1)-(3).

Parameter estimation

We first study the problem with some simplifications in order to estimate the unknown parameters a, p 0 , κ, and δ 2 . First, we assume that the sample size is much larger than the width of the interfacial layer and set M = +∞ so that the domain is infinite. Next, assume that the dielectric permittivity is constant throughout the interfacial layer: ε(z) = ε W , where ε W = 80 is the bulk value. Recent experiments show that within a few nanometers of the hydrophilic surface, the permittivity drops to about ε int = 2 [START_REF] Fumagalli | Anomalously low dielectric constant of confined water[END_REF]. On the other hand, we expect the interfacial layer to be several hundred microns wide. Because of this difference in length scales, it is reasonable to assume in this initial approach that ε(z) = const. The exact solution in this case is (see the Appendix for the calculation):

p(z) = p 0 √ λ(β 2 + 1) β + sinh ω , (13)
Φ(z) = 2 √ κδ 2 ε 0 ε W tanh -1 β tanh(ω/2) -1 β 2 + 1 -tanh -1 β -1 β 2 + 1 , (14)
with

ω(z; a, λ) = β 2 + 1 ε 0 ε W κ z + c, (15)
λ = δ 2 ε 0 ε W p 2 0 , (16)
β(a, λ) = a √ λ , (17)
c(a, λ) = tanh -1 a 2 -a + λ √ a 2 + λ (a -1) 2 + λ . ( 18
)
The goal of this section is to estimate the unknown quantities p 0 , a, δ 2 , and κ which determine the solution ( 14)-(18). Equation [START_REF] Jabs | Self-organization at aqueous colloid-membrane interfaces and an optical method to measure the kinetics of exclusion zone formation[END_REF] implies p 0 = -E 0 /(ε 0 ε W ), where E 0 is the electric field at the hydrophilic surface. We can therefore estimate p 0 using the value

E 0 = -40 V m -1 [7, figure 4c].
To estimate the remaining parameters, we make several assumptions. First, we suppose that the boundary condition p = p 0 is a stationary solution to [START_REF] Liu | Nonthermal and reversible control of neuronal signaling and behavior by midinfrared stimulation[END_REF]. In this case p is approximately constant near the hydrophilic surface at z = 0. This assumption gives λ = λ(a).

Next, observe that both p(z) and Φ(z) depend on z only through the function ω(z; a, λ) defined in (18). The length scale of the solution is determined by β, and we select a so that β (a, λ(a)) gives the largest possible length scale. This will give the largest interfacial layer in the solution.

Finally, it remains to estimate the parameter κ. Observe that p = 0 at z = 0 (from the first assumption) and at z = +∞, where p = 0. Between these two endpoints, p has a maximum, say at z 0 . Roughly speaking, for z < z 0 (near the hydrophilic surface), the polarization profile p(z) resembles an exponentially decaying function, and for z > z 0 , p(z) begins to level out. The point z = z 0 can then be understood as the boundary between the interfacial layer and the rest of the cell. In order to estimate κ, we will now first approximate z 0 = L IF , where L IF is an experimental measurement of the interfacial layer thickness, and then work backwards.

There are many measurements of the interfacial layer thickness in the literature [START_REF] Jian Ming Zheng | Surfaces and interfacial water: Evidence that hydrophilic surfaces have long-range impact[END_REF][START_REF] Chen | Force field measurements within the exclusion zone of water[END_REF][START_REF] Esplandiu | Electrophoretic origin of long-range repulsion of colloids near water/nafion interfaces[END_REF][START_REF] István | Exclusion-zone dynamics explored with microfluidics and optical tweezers[END_REF][START_REF] Jabs | Self-organization at aqueous colloid-membrane interfaces and an optical method to measure the kinetics of exclusion zone formation[END_REF][START_REF] Florea | Long-range repulsion of colloids driven by ion exchange and diffusiophoresis[END_REF]. The authors of [START_REF] Florea | Long-range repulsion of colloids driven by ion exchange and diffusiophoresis[END_REF] find that the layer width grows with time, up to a few millimeters. Since our model is stationary, the solution (p, Φ) in ( 14) represents the eventual, long-time state, and we expect the layer width to be large. We therefore approximate L IF = 2 mm.

With the above assumptions, we obtain the following parameter estimates:

p 0 = 2.8 × 10 -8 C m -2 , (19)
δ 2 = 10 -25 m 2 N -1 , (20)
a = 4 3 , (21)
κ = 1.5 × 10 4 Nm 4 C -2 . ( 22
)
We also find that at the edge of the interfacial layer, the polarization is at one-third of its maximum value. That is, p(z = L IF ) = p 0 /3. Figure 1 shows the solution ( 14)-( 18) for the parameters (19). Though we have made several simplifications, this exact solution also provides an excellent prediction of the electric potential at the surface. Experiments show [14, figure 3a] that the electric potential at the surface is on the order of -60 mV, and with parameters as above the model predicts Φ(0) = -68 mV.

With correction to permittivity

We consider again the problem ( 10)-( 12), subject to (1)-( 3), without the simplifying assumptions of the previous section. We use the parameter values ( 19)-( 22) and choose the domain size to be M = 1 cm. Additionally, we allow the permittivity to depend on the distance z from the surface, with

ε(z) = ε int + ε W -ε int 1 + exp(-α(z -ẑ)) . (23)
In ( 23), ε int = 2 is the value of the permittivity in the interface, and the distance ẑ is on the order of a few molecular lengths [START_REF] Dmitry | Dielectric susceptibility of water in the interface[END_REF]. The profile of ε(z) is shown in figure 2a, with ẑ = 10 nm and α = 10 7 m -1 .

Comparing figures 1 and 2, we find that the polarization and potential profiles are nearly identical. Therefore, we can conclude a posteriori that the approximation ε(z) ≈ ε W made in the previous section was reasonable. This is not surprising, since in (23), the region where ε ≈ ε int is only about 10 nm wide, orders of magnitude smaller than the width of the interfacial layer.

Conclusion

We have developed a simple model for the electric polarization and potential within the interfacial layer of water near a hydrophilic surface. We postulated an energy law with a double-well potential describing the two preferred states of the polarization, derived the governing equations, and studied the solutions in two regimes. First, we studied the problem on an infinite domain, with constant dielectric permittivity, employing experimental measurements of the electric field and the layer thickness in order to estimate the phenomenological parameters which appear in the energy. We then used the found parameter values to study the same problem on a finite domain, with varying permittivity. The polarization and potential profiles in both regimes are exponentially decaying and show good agreement with experiment. Crucially, our model predicts that the electric potential at the hydrophilic surface is -68 mV for the infinite domain, or -61 mV for the finite domain. Experiment shows [START_REF] Jian Ming Zheng | Surfaces and interfacial water: Evidence that hydrophilic surfaces have long-range impact[END_REF] that the electric potential at the surface is about -60 mV, matching our model prediction very well.

The proposed model is one-dimensional and neglects ionic effects. This work therefore does not rule out any of the proposed explanations for the formation of the interfacial layer. In an upcoming work, we will expand the current model to include the possible physical mechanisms responsible for the interfacial water phenomenon.

The present work sets our long term goal to develop a model for understanding the role of interfacial water in biological systems. An important class of such systems are excitable cellular media, such as neuronal cells and heart cells that mediate their functions via electrical-chemical signals. Since interface water exhibits non-neutral potential then it is reasonable to ask whether the standard neuronal models (e.g. Hodgkin-Huxley), which assume neutral water and ions as the main mediators for excitability, are sufficiently correct. A fundamental feature of interfacial water is that it reacts to light (including infrared) by expanding the size of the interfacial layer. Interestingly, recent neuronal experiments have shown that mid-infrared light (by carefully avoiding thermal contributions) increases neuronal excitability, thus hinting at the fact that interfacial water is at play [START_REF] Liu | Nonthermal and reversible control of neuronal signaling and behavior by midinfrared stimulation[END_REF]. In this context our model opens a novel avenue of enquiry, which will help clarify if excitable cellular media and in general biological systems exploit the energy in interfacial water to mediate their cellular functions.

for µ = κδ 2 p 2 0 L 2 , λ = δ 2 ε 0 ε W p 2 0 .
(A.9)

Multiply (A.6) by 2p z and integrate once to obtain

µ(p z ) 2 = p2 (p -a) 2 + λ + c 1 . (A.10)
We first assume that we can take the integration constant c 1 to be zero so that dp/dz → 0 as z → +∞; we will later verify that this is the correct choice of c 1 . Then the only constant solution to (A.10) is the nonpolar state p = 0, and (A.11) can be rewritten

pz p p √ λ -β 2 + 1 -1/2 = ± λ µ (A.11) for β = a √ λ . (A.12) Integrate (A.11) with Mathematica to obtain tanh -1     1 -β p √ λ -β β 2 + 1 p √ λ -β 2 + 1     = ∓ a 2 + λ µ z + c 2 . (A.13)
In order to satisfy the boundary condition at z = +∞, we must take the plus sign on the right side of (A.13). Also, (A.2) implies

c 2 = tanh -1 a 2 -a + λ √ a 2 + λ (a -

Figure 1 .

 1 Figure 1. The solution (14)-(18) for the polarization p (a) and the electric potential Φ (b). The polarization and electric potential profiles have the qualitatively the shape that appears in experiments, and the value of the potential at the surface is Φ(0) = -68 mV.

Figure 2 .

 2 Figure 2. (a): Dielectric permittivity profile defined in (23). (b) and (c): Numerical solution for p and Φ, respectively, with M = 1 cm, ε = ε(z) as in (23), and parameters as in (19). The value of the potential at the surface is Φ(0) = -61 mV.

1 ) 2 2

 122 + λ .(A.[START_REF] Jian Ming Zheng | Surfaces and interfacial water: Evidence that hydrophilic surfaces have long-range impact[END_REF] Equation (A.13) can be rewrittenp √ λ = β + β ± (β 2 + 1)tanh ω sech ω β 2 sech 2 ω -tanh 2 ω, choice of c 1 = 0 was correct. Now, define ω * = sinh -1 β and note thatβ 2 sech 2 ω * -tanh 2 ω * = 0, (A.18) tanh ω * sech ω * = β β 2 + 1 . (A.19)If we take the plus sign in (A.15), then lim ω→ω * p(ω) = +∞. The solution p should be continuous for ω > c 2 , and we therefore take the minus sign in (A.15) to get the solutionp √ λ = β + β -(β 2 + 1)tanh ω sech ω β 2 sech 2 ω -tanh 2 ω = β ω IF = sinh -1 (7 √2) and ε W = 80, (A.28) impliesκ = 3.7 × 10 9 Nm 2 C -2 L 2 IF . (A.32)The width of the interfacial layer can grow to almost 3 mm over the course of a few hours[START_REF] Florea | Long-range repulsion of colloids driven by ion exchange and diffusiophoresis[END_REF]. Using the estimateL IF = 2mm, (A.33) from equation (A.32) we finally estimate κ = 1.5 × 10 4 Nm 4 C -2 . (A.34) Using (A.4), we find that the polarization p(z) (with dimension) is p(z) = p 0 √ λ(β 2 + 1) β + sinh ω . (A.35)The electric potential Φ in[START_REF] Jian Ming Zheng | Surfaces and interfacial water: Evidence that hydrophilic surfaces have long-range impact[END_REF] can then be computed from Poisson's equation, boundary condition Φ(+∞) = 0.

Acknowledgments

SR and MD are grateful to Prof. Vera Maura Fernandes de Lima for very insightful discussions on interfacial water. SR and AZ acknowledge support from Ikerbasque (The Basque Foundation for Science). AE, SR and AZ acknowledge the support of the Basque Government through the BERC 2018-2021 program and the Spanish State Research Agency through BCAM Severo Ochoa excellence accreditation SEV-2017-0718 and through project RTI2018-093860-B-C21 funded by (AEI/FEDER, UE) and acronym "MathNEURO". MD and SR acknowledge the support of Inria via the Associated Team "NeuroTransSF". AZ acknowledges the support of project PID2020-114189RB-I00, acronym "LICI" funded by Agencia Estatal de Investigación (PID2020-114189RB-I00 / AEI / 10.13039/501100011033).

Appendix

In this appendix, we show the calculations to obtain the solution ( 14 The dimensionless polarization p(z) depends on the phenomenological parameters λ, µ, and a. We now make several assumptions in order to estimate these parameters. First, suppose that So λ < 1 4 , and because λ > 0 by (A.9), we see that 1 < a < 2 as well. Note that δ = δ(a) by combining (A.9) and (A.22).

Next, observe that the quantity β 2 + 1 controls the length scale of the problem through ω in (A.20). This length scale is maximized when β is minimized. Using (A.22), we can write

which is minimized at

Under the assumptions (A.22) and (A.24), the solution (A.15) can be written

From (A.9) and (A.22), we also obtain the estimate

The only phenomenological parameter left to estimate is κ. With a and λ chosen as above, (A.6) is

Observe that pzz = 0 at the boundaries z = 0, +∞. In the interior, pzz > 0 since 0 < p < 1. Therefore, pzz has a maximum at some ẑ, 0 < ẑ < ∞. In the region z < ẑ near the surface, the polarization is quickly decreasing from the boundary value of 1. Away from the surface, z > ẑ, the polarization has decayed close to zero. The distance ẑ from the surface where pzz is maximized therefore gives a good estimate of the width of the interfacial layer.

We will suppose that pzz is maximized at z = L IF , where L IF is an experimental measurement of the width of the interfacial layer. Let ω IF = ω(z = L IF /L):


Jean-François Prefix Suffix

Sophie Prefix

Jean-François Culus
email: jean-francois-culus@espe-martinique.fr

CSPs All Are Approximable Within a Constant Differential Factor

Keywords:

Only a few facts are known regarding the approximability of optimization CSPs with respect to the differential approximation measure, which compares the gain of a given solution over the worst solution value to the instance diameter. Notably, the question whether is approximable within any constant factor is open in case when or . Using a family of combinatorial designs we introduce for our purpose, we show that, given any three constant integers , and , reduces to with an expansion of on the approximation guarantee. When , this implies together with the result of Nesterov as regards

[1] that for all constant integers , is approximable within factor .

Introduction

Optimization Constraint Satisfaction Problems

Thereafter, given a positive integer N , we denote by [N ] the discrete interval {1, . . . , N}. Optimization Constraint Satisfaction Problems (CSPs) over an alphabet Σ consider a set {x 1 , . . . , x n } of variables and a set {C 1 , . . . , C m } of constraints, where the variables have domain Σ, and the constraints consist of (non constant) predicates applied to tuples of variables. Most often, a positive weight is associated with each constraint C i . The goal is then to optimize over Σ n an objective function of the form

m i=1 w i C i = m i=1 w i P i (x Ji ) = m i=1 w i P i (x i1 , . . . , x i k i )
where for all i ∈ [m], P i : Σ ki → {0, 1}, J i = (i 1 , . . . , i ki ) ⊆ [n], and w i > 0.

For example, the Satisfiability Problem (Sat) is the boolean CSP where constraints are disjunctive clauses. In Lin-q, the alphabet is Z q = Z/qZ, and a constraint is a linear equation modulo q. In this paper, given two universal constant integers q, k ≥ 2, we consider the optimization CSP k CSP-q where Σ has size q, each constraint depends on at most k variables, and functions P i are allowed to take rational values. 1 In the sequel, given an instance I of k CSP-q, we will assume either Σ = [q] or Σ = Z q , and that the optimization goal is to maximize. These assumptions are without loss of generality. 2 .

k CSP-q most often becomes harder as k or q grows. On the one hand, given two integers h ≥ 2 and k > h, h CSP-q is a special case of k CSP-q. On the other hand, given two integers p ≥ 2 and q > p, any surjective map from [q] to [p] can be used to convert a function on [p] k to a function on [q] k . The alphabet size more accurately has a logarithmic impact on the constraint arity: if κ = log p q , then any surjective map from [p] κ to [q] similarly allows to convert a function on [q] k to a function on [p] κk . As 2 CSP-2 is NP-hard [START_REF] Garey | Some simplified NP-complete graph problems[END_REF], a major issue as regards k CSP-q consists in charactering its approximation degree.

Their Differential Approximability

Given an instance I of an optimization problem Π, we denote by v(I, .) its objective function, by opt(I) and wor(I) respectively the best and the worst solution values on I. Approximation algorithms aim at providing within polynomial time solution values proved to be relatively close to the optimum solution value, where the proximity to opt(I) is defined with respect to a specific measure. In this paper, we consider the differential approximation measure (see [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] for an introduction). On I, the differential ratio reached at a given solution x is the ratio: v(I, x)wor(I) opt(I)wor(I)

Given ρ ∈]0, 1],
x is said ρ-approximate if this ratio is at least ρ. A polynomial time algorithm A is a ρ-approximation algorithm for Π if it returns on every instance of Π a solution with differential ratio at least ρ. Finally, Π is approximable within factor ρ whenever such an algorithm exists. Only a few facts are known regarding the approximability of k CSP-q within a constant differential factor. On the one hand, the restrictions of Max Sat and Min Sat to unweighted instances (i.e., to instances in which weights w i all are equal to 1) are not approximable within any constant factor unless P = NP [START_REF] Escoffier | Differential approximation of MIN SAT, MAX SAT and related problems[END_REF]. On the other hand, for 2 CSP-2, the semidefinite programming-based algorithm 1 CSPs in which constraints take non-boolean values are commonly called generalized CSPs in the literature. However, given a function P : Σ k → Q with minimal value P * , a constraint P (xJ i ) coincides, up to an additive constant term, with the combination

v∈Σ k (P (v) -P * ) × (xJ i = v) of constraints.
Thus when k and q are universal constants, we may indifferently consider functions with codomain {0, 1} or Q. 2 For the latter assumption, consider that minimizing

m i=1 wiPi(xJ i ) reduces to maximize m i=1 wi × -Pi(xJ i ).
of Goemans and Williamson [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF] produces solutions with expected differential ratio at least 2π/2 > 0.429 [START_REF] Nesterov | Semidefinite relaxation and nonconvex quadratic optimization[END_REF], and the algorithm can be derandomized [START_REF] Hariharan | Derandomizing approximation algorithms based on semidefinite programming[END_REF].

A common way to exhibit new approximability lower and upper bounds for a given optimization problem consists in reducing to or from another optimization problem for which approximability bounds are known: Definition 1 (Informal). An optimization problem Π D-reduces to another optimization problem Π if one can derive from any ρ-approximation algorithm A for Π a γ × ρ-approximation algorithm for Π, where γ is some positive quantity. When this occurs, γ is called the expansion of the reduction.

In particular, it is possible to derive from the (2π/2)-approximation algorithm for 2 CSP-2 a (1π/4)-approximation algorithm for 3 CSP-2: Proposition 1. 3 CSP-2 D-reduces to E2 Lin-2 with an expansion of 1/2 on the approximation guarantee.

Proof (sketch). The discrete Fourier transform allows to convert any instance I of 3 CSP-2 over {0, 1} to an instance J of Max 3 Lin-2 such that v(J, .) coincides, up some constant term, with v(I, .). From such an instance J, build an instance H of 2 Lin-2 by removing the equations of odd arity. Let W refer to the total weight of such equations in J. Then for all x ∈ {0, 1} n , v(J, x) + v(J, x) = 2 × v(H, x) + W , where x refers to the componentwise negation of x. Assume that x ∈ {0, 1} n is ρapproximate on J. Then the preceding equality taken at x, an optimum solution on J, and a worst solution on H allows to conclude that solution x or x that performs the best objective value on J is ρ/2-approximate on J.

Still, the question whether k CSP-q is approximable within any constant factor remains open in case when q ≥ 3 or k ≥ 4.

Outline

Given an integer k ≥ 2 and two integers q, p ≥ 2 with q > p, we address the question whether k CSP-q D-reduces to k CSP-p. We more specifically study the expansion of a specific reduction: given an instance I of k CSP-q, the reduction basically consists in considering the restrictions of I to solutions sets of the form T n where T is a p-element subset of Σ. The analysis we propose, though, requires to restrict to the case when p ≥ k.

In the next section, we introduce a family of combinatorial designs (Definition 2) that provides some lower bound γ(q, p, k) for the expansion of the reduction (Theorem 1). Section 3 is then dedicated to the exhibition of such combinatorial designs. Using a recursive construction for the case when p = k (Theorem 2), we show that 1/(qp + k/2) k is a proper lower bound of for γ(q, p, k). Therefore, we obtain the following conditional approximation result: Corollary 1. Given any three integers k ≥ 2, p ≥ k and q > p, k CSP-q D-reduces to k CSP-p with an expansion of 1/(q-p+k/2) k on the approximation guarantee. The reduction involves O(q p ) instances of k CSP-p.

The question whether k CSP-q is approximable within some constant factor consequently reduces to the consideration of integers k, q such that k ≥ q ≥ 2. Most importantly, it follows from Nesterov's result as regards 2 CSP-2 (we more specifically refer to Theorem 2.3, Theorem 3.3 and Corollary 3.4 of [START_REF] Nesterov | Semidefinite relaxation and nonconvex quadratic optimization[END_REF]) that for all integers q ≥ 2, 2 CSP-q is approximable within a constant factor: Corollary 2. For all integers q ≥ 2, 2 CSP-q is approximable within factor (2π/2)/(q -1) 2 .

Reducing the Alphabet Size of a CSP Instance

Let k ≥ 2, p ≥ 2 and q > p be three integers, and I be an instance of k CSP-q over alphabet [q]. Thereafter, P p ([q]) refers to the set of the p-element subsets of [q].

Given S = (S 1 , . . . , S n ) ∈ P p ([q]) n , any set {π S,j :

S j → [p] | j ∈ [n]
} of bijections allows to interpret the restriction of I to solutions in S as an instance of k CSP-p. Therefore, a natural way to derive approximate solutions on I from a hypothetical algorithm A for k CSP-p consists in restricting I to solution subsets S ∈ P p ([q]) n . The standard approximation measure evaluates the performance of a given solution x by the ratio v(I, x)/opt(I). In [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF], the authors study the randomized reduction that consists in picking S ∈ P p ([q]) n uniformly at random, and then using A to compute a solution x ∈ S. They show that, provided that the goal on I is to maximize and I is such that

w i P i ≥ 0, i ∈ [m]
, the expected value of max y∈S {v(I, y)} over all S ∈ P p ([q]) n is at least (p/q) k × opt(I). Accordingly, picking S ∈ P p ([q]) n uniformly at random, and then computing a solution x ∈ S with value at least ρ × max y∈S {v(I, y)}, one gets a solution with expected value at least (p/q) k ρ × opt(I). The reduction therefore preserves the expected standard ratio up to a multiplicative factor of (p/q) k .

Given T ∈ P p ([q]), we denote by I(T ) the restriction of I to solution set T n . Then similarly to [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF], we analyse the reduction that consists in using A to compute for all T ∈ P p ([q]) an approximate solution x(T ) on I(T ), and then returning a solution x(T ) that performs the best objective value.

Seeking Symmetries in the Solution Set

We assume w.l.o.g. that the goal on I is to maximize, in which case the extremal values on I and on subinstances I(T ) trivially satisfy:

opt(I) ≥ opt(I(T )) ≥ wor(I(T )) ≥ wor(I), T∈ P p ([q]) (1)
Now assume that for all T ∈ P p ([q]), we are given a solution x(T ) ∈ T n that is ρ-approximate on I(T ). Then for all T * ∈ P p ([q]), we have:

max T ∈Pp([q]) {v(I, x(T ))} ≥ v(I, x(T * )) ≥ ρ × opt(I(T * )) + (1 -ρ) × wor(I(T * )) ≥ ρ × opt(I(T * )) + (1 -ρ) × wor(I) by (1) (2)
Eventually assume that T * is a set in P p ([q]) that contains a solution with optimal value over {T n | T ∈ P p ([q])}. Then, provided that opt(I(T * )) is δ-approximate on I, one gets the following connection with opt(I(T )):

max T ∈Pp([q]) {v(I, x(T ))} -wor(I) ≥ ρ × (opt(I(T * )) -wor(I)) (2) ≥ ρ × δ × (opt(I) -wor(I)) (3)
Hence, if we are able to compare-in a differential approximation manneropt(I(T * )) to opt(I), then we can deduce from approximate solutions on subinstances I(T ) approximate solutions on I. We thus shall seek a lower bound for the differential ratio reached on I at opt(I(T * )).

Let x * be an optimal solution of I. Then one way to obtain such a lower bound consists in exhibiting two solution multisets X = (x 1 , . . . , x R ) and Y = (y 1 , . . . , y R ) of the same size R, and that satisfy the following conditions:

X ⊆ {T n | T ∈ P p ([q])} (4) R * |{r ∈ [R] | y r = x * |} ≥ 1 (5) |{r ∈ [R] | x r Ji = v}| = |{r ∈ [R] | y r Ji = v}|, v ∈ [q] Ji , i ∈ [m] (6)
Requirements ( 4), ( 5) and ( 6) respectively ensure that X exclusively considers solutions of subinstances I(T ), x * occurs at least once in Y, and each constraint P i (x Ji ) of I is evaluated on the same collection of |J i |-tuples over solution multisets X and Y. Requirement (6) thus ensures that the sum of solution values over X and Y are identical. Provided that such a pair (X , Y) exists, we have:

opt(I(T * )) ≥ R r=1 {v(I, x r )}/R by definition of T * , and (4) = R r=1 {v(I, y r )}/R by (6) ≥ R * × opt(I)/R + (R -R * ) × wor(I)/R by (5) (7)
Thus opt(I(T * )) is R * /R-approximate on I. Therefore, one shall seek such pairs (X , Y) on which the ratio R * /R is as hight as possible.

This is precisely what we do, and this is why we restrict our analysis to the case when k ≤ p. Indeed, e.g. assume that J 1 = (1, . . . , k) and (x * 1 , . . . , x * k ) = (1, . . . , k). Then by ( 6) and ( 5), X shall contain at least R * > 0 solutions x r with (x r 1 , . . . , x r k ) = (1, . . . , k). If k > p, then such solutions violate condition (4). Hence, from now on, we assume q > p ≥ k.

Partition-Based Solution Multisets

Solution x * induces a partition of [n] into q-possibly empty-subsets depending on the q possible values taken by its coordinates. Given c ∈ [q], we denote by V c the set of indices j ∈ [n] such that x * j = c. We restrict our solution multisets to vectors x that satisfy

x * j = x * h ⇒ x j = x h , j, h ∈ [n].
It is thus possible to identify X and Y with two arrays Ψ and Φ with q columns, coefficients in [q], and the same number R of rows, where: each row Ψ r = (Ψ 1 r , . . . , Ψ q r ) of Ψ gives rise in X to the vector of [q] n that satisfies for every c ∈ [q] that its coordinates with index in V c all are equal to Ψ c r ; Y is derived from Φ in the exact same way. Formally, we define π x * : [q] q → [q] n by

π x * (u) Vc = (u c , . . . , u c ), c ∈ [q] and X , Y by X = (π x * (Ψ r ) | r ∈ [R]) and Y = (π x * (Φ r ) | r ∈ [R]). Given i ∈ [m],
we denote by c i,1 , . . . , c i,hi the distinct values taken by the coordinates of x * with index in J i , by H i = {c i,1 , . . . , c i,hi } the set of such values, by Ψ Hi and Φ Hi the restrictions of Ψ and Φ to their columns with index in H i . Then solution multisets X and Y meet requirements (4), ( 5) and ( 6) of Sect. 2.1 iff arrays Ψ and Φ satisfy:

|{Ψ 1 r , . . . , Ψ q r }| ≤ p, r ∈ [R] (8) R * |{r ∈ [R] | Φ r = (1, . . . , q)}| ≥ 1 (9) |{r ∈ [R] | Ψ Hi r = v}| = |{r ∈ [R] | Φ Hi r = v}|, v ∈ [q] |Hi| , i ∈ [m] (10)
Hence, if we are aware of such a pair of arrays, then we know by ( 7) that opt(I(T * )) is R * /R-approximate. In light of these observations, we introduce the following families of combinatorial designs and their associated numbers: Definition 2. Let k ≥ 2, p ≥ k and q ≥ p be three integers. Then given any two integers R ≥ 1 and R * ∈ [R], we define Γ (R, R * , q, p, k) as the (possibly empty) set of pairs (Ψ, Φ) of arrays with R rows, q columns, and coefficients in [q] that satisfy the following:

1. the components of each row of Ψ take at most p distinct values; 2. (1, . . . , q) occurs R * times as a row in Φ; 3. for all J = {c 1 , . . . , c k } ⊆ [q] with |J| = k, subarrays Ψ J = (Ψ c1 , . . . , Ψ c k ) and Φ J = (Φ c1 , . . . , Φ c k ) coincide up to the ordering of their rows.

Furthermore, we define γ(q, p, k) as the greatest number γ ∈ [0, 1] for which there exist two natural numbers R, R * such that R * /R = γ and Γ (R, R * , q, p, k) = ∅. Table 1. Pairs of arrays that achieve γ(4, 3, 2) and γ(5, 3, 2).

Table 1 pictures two such combinatorial designs. Since cardinalities |H i | may be at most min{q, k} = k, by requirement 3, a pair (Ψ, Φ) ∈ Γ (R, R * , q, p, k) does satisfy (10) regardless of the precise instance I of k CSP-q and the precise solution x * of I we consider. By [START_REF] Charikar | Near-optimal algorithms for maximum constraint satisfaction problems[END_REF], this implies that γ(q, p, k) is a proper lower bound for the differential ratio reached on I at opt(I(T * )). We thus have established the following: Lemma 1. For all integers k ≥ 2, p ≥ k and q > p, on any instance of k CSP-q, solutions that perform the best objective value among those whose coordinates take at most p distinct values are γ(q, p, k)-approximate.

To conclude, according to inequality (3), Lemma 1 also establishes that γ(q, p, k) is a proper lower bound for the expansion of our reduction: Theorem 1. For all integers k ≥ 2, p ≥ k and q > p, k CSP-q D-reduces to k CSP-p with an expansion of γ(q, p, k) on the approximation guarantee. The reduction involves O(q p ) instances of k CSP-p.

A Lower Bound for Numbers γ(q, p, k)

It remains us to exhibit lower bounds for numbers γ(q, p, k). To do so, we mainly present a recursive construction for the case when p = k. But first, we mention a few combinatorial identities that are involved in the analysis of this construction.

We define:

T (a
T (a, b) = 2 b a-1 b + T (a -1, b -1) (13) = 2 b a b -T (a, b -1) (14) = 2 a-1 c=b T (c, b -1) + 1 (15)
Proof (sketch). Recursions ( 13) and ( 14) are obtained applying Pascal's rule to coefficients of the form respectively a r and a-1-r b-r . Identity (15) can then be deduced from those recursions. Proof (sketch). By induction on integer ba.

A Recursive Construction for Families Γ (R, 1, q, k, k)

This section is dedicated to the proof of the following Theorem:

Theorem 2. Let k ≥ 2 and q ≥ k be two integers. Then γ(q, k, k) is equal to 1 if q = k, and bounded below by 2/(T (q, k) + 1) otherwise.

The case when q = k is trivial, considering Ψ = Φ = {(1, . . . , k)}. For greater integers qk, the argument relies on the following Lemma: k,k). We assume w.l.o.g. that (1, . . . , q -1) occurs at row 1 in Φ. Our goal is to add in arrays Ψ and Φ a single new column, and as few rows as possible, so as to obtain a new pair (Ψ, Φ) of arrays with q columns and coefficients in [q] that meets requirements 1, 2, 3 of Definition 2.

Lemma 2. Let k ≥ 2, q > k, R * ≥ 1 and R ≥ R * be four integers such that Γ (R, R * , q -1, k, k) = ∅. Then Γ (R + T (q -1, k -1), 1, q, k, k) = ∅. Proof. Let (Ψ, Φ) ∈ Γ (R, R * , q -1,

Table 2. Construction of a pair of arrays in

Γ (R + T (q -1, k -1), 1, q, k, k) starting with a pair (Ψ, Φ) ∈ Γ (R, R * , q -1, k, k) with Φ1 = (1, . . . , q -1).
The construction is described in Table 2. We make a few comments before proving its rightness. Step 1 first inserts a qth column in the arrays. If we set Ψ q to Ψ 1 and Φ q to Φ 1 , then (Ψ, Φ) trivially fulfils requirements 1 and 3. However, as (1, . . . , q) mu st occur at least once as a row in Φ, we assign value q rather than Φ 1 1 to Φ q 1 . As a result, (Ψ, Φ) violates requirement 3. Hence, during Step 2, we insert new rows in the arrays until they satisfy this requirement.

Let J = {c 1 , . . . , c k-1 } be a (k -1)-element subset of [q -1], and v = (c 1 , . . . , c k-1 ). After Step 1, row 1 is the single row of subarray (Φ J , Φ q ) that coincides with (v, q), while there is no such row in (Ψ J , Ψ q ). As (Φ J 1 , Φ 1 1 ) = (v, 1) while (Φ, Ψ ) ∈ Γ (R, R * , q -1, k, k), (Φ J , Φ q ) symmetrically coincides with (v, 1) on one less row than (Ψ J , Ψ q ) does. Iteration h = k -1 corrects this precise imbalance when it inserts row vectors (α(J), q) in Ψ and (α(J), 1) in Φ.

However, this iteration also introduces new violations of requirement 3. Notably, let s ∈ [k -1], and v = (c 1 , . . . , c s-1 , q, c s+1 , . . . , c k-1 ). Then iteration h = k -1 inserts in each array a new row u with u J = v each time it selects a (k -1)-element subset H of [q -1] with c 1 , . . . , c s-1 , c s+1 , . . . , c k-1 ∈ H and c s / ∈ H. Since there are q -1 -(k -1) = qk such subsets, we deduce that at the end of this iteration, vectors (v, q) and (v, 1) occur respectively qk and 0 times as a row in (Ψ J , Ψ q ), while the converse holds for (Φ J , Φ q ). Iteration h = k -2 corrects this precise imbalance when it inserts qk copies of row vectors (α(J\{c s }), 1) and (α(J\{c s }), q) in respectively Ψ and Φ. More generally, for all h ∈ {0, . . . , k -1}, given any v ∈ {c 1 , q} × . . . × {c k-1 , q} with exactly h coordinates in [q -1] and any a ∈ {1, q}, iteration h ensures that (v, a) occurs the same number of times as a row in (Ψ J , Ψ q ) and (Φ J , Φ q ). Table 3. The recursive construction for families Γ ((T (5, 2) + 1)/2, 1, 5, 2, 2) and Γ ((T (4, 3) + 1)/2, 1, 4, 3, 3) of combinatorial designs.

We now prove that, at the end of the process, (Ψ, Φ) ∈ Γ (R , 1, q, k, k) where R = R + T (q -1, k -1). By construction, the resulting arrays satisfy that:

-their number R of rows is R + k-1 h=0 q-1 h q-2-h k-1-h = R + T (q -1, k -1)
; -in Ψ , the coefficients of every row take at most k distinct values; -in Φ, row 1 is the single row that coincides with (1, . . . , q). It remains us to show that (Ψ, Φ) fulfils requirement 3. Let J = (c 1 , . . . , c k ) be a strictly increasing sequence of integers in [q], and v be a vector of [q] k . We shall establish that subarrays Ψ J and Φ J coincide with v on the same number of rows. The case when q / ∈ J is trivial. Thus assume c k = q. We consider two cases:

• v / ∈ {c 1 , q} × . . . × {c k-1 , q} × {1, q}. Ψ J r = v or Φ J r = v may not occur unless r ∈ [R]. Let r ∈ [R] and let K = (c 1 , . . . , c k-1 , 1). Then Ψ J r = Ψ K r , while Φ J r = Φ K r unless r = 1, in which case Φ J 1 = v = Φ K 1 .
Since the original pair of arrays belongs to Γ (R, R * , q -1, k, k), we deduce that Ψ J and Φ J indeed coincide with v on the same number of rows.

• v ∈ {c 1 , q} × . . . × {c k-1 , q} × {1, q}. If (v 1 , . . . , v k-1 ) = (c 1 , . . . , c k-1 ), then
we already argued that iteration h = k -1 of Step 2 corrects the imbalance induced by assignment Φ q 1 = q. Otherwise, let L refer to the set of indices c s ∈ {c 1 , . . . , c k-1 } such that v s = c s , and let = |L|. As ≤ k -2, Ψ J r = v or Φ J r = v may not occur unless r > R. So consider an iteration h ∈ {0, . . . , k-1} of Step 2. For each h-element subset H of [q -1] with L ⊆ H and H\L ⊆ [q -1]\J, this iteration generates q-2-h k-1-h rows u with u J = v. If v k = q (resp., v k = 1), then these rows occur in Ψ (resp., in Φ) iff h has the same parity as k -1. Since there are q-k h-such subsets H of [q -1], we deduce:

|{r ∈ [R ] | Ψ J r = v}| -|{r ∈ [R ] | Φ J r = v}| = ± k-1 h= (-1) k-1-h q-2-h k-1-h q-k h- = ± k-1- r=0 (-1) k-1--r q-2--r k-1--r q-k r = ±S(q -k, q -2 -, k -1 -) Now we know from Property 2 that S(q -k, q -2 -, k -1 -) is equal to k-2- k-1-, which is 0. We conclude that (Ψ, Φ) indeed belongs to Γ (R + T (q - 1, k -1), 1, q, k, k).
The proof of Theorem 2 is straightforward from Lemma 2. Namely, given two integers k ≥ 2 and q ≥ k, we consider the following recursive construction:

1. Set Ψ = {(1, . . . , k)} and Φ = {(1, . . . , k)}. 2. For a = k + 1 to q, apply construction underlying Lemma 2 to (Ψ, Φ).

Table 3 illustrates the construction when k ∈ {2, 3}. On the one hand, in view of Lemma 2, the resulting pair (Ψ, Φ) of arrays belongs to Γ (R, 1, q, k, k) where

R = 1 + q a=k+1 T (a -1, k -1) = 1 + q-1
a=k T (a, k -1) On the other hand, by (15), we have:

1 + q-1 a=k T (a, k -1) = 1 + (T (q, k) -1)/2 = (T (q, k) + 1)/2
This completes the proof of Theorem 2.

Deduced Approximation Results

Let k ≥ 2, p ≥ k and q > p be three integers. If p = k, then Theorem 2 together with Theorem 1 provides a lower bound of 2/(T (q, k) + 1) for the expansion of our reduction from k CSP-q to k CSP-k. We seek an estimate of 2/(T (q, k)+1). Proof. Applying recursions first (14), and then (13), one gets equality:

T (a, b) + 1 = 2 b a b -2 b-1 a-1 b-1 -T (a -1, b -2) + 1 (16)
On the one hand, we deduce again from (13) that

T (a -1, b -2) -1 ≥ T (a -b + 1, 0) -1 = 0. On the other hand, we can rewrite 2 b a b -2 b-1 a-1 b-1 as: 2 b a b -2 b-1 a-1 b-1 = 2(a -b/2) × 2 b-1 /b! × b-2 i=0 (a -1 -i)
On the one hand, 2 b-1 /b! ≤ 1. On the other hand, the inequality of arithmetic and geometric means yields inequality

b-2 i=0 (a -1 -i) ≤ (a -b/2) b-1 .
Table 4. Numbers γ(q, p, k) and γE(q, p, k) for some triples (q, p, k). These values (and the underlying pairs of arrays) were calculated by computer.

Hence, when p = k, the expansion of the reduction is at least 1/(qk/2) k . In particular, if k = 2, then 2/(T (q, 2) + 1) = 1/(q -1) 2 . As 2CSP -2 is approximable within factor 2-π/2, Corollary 2 thus holds. When p > k, simply observe that we have:

γ(q, p, k) ≥ γ(q -p + k, k, k) ≥ 2/(T (q -p + k, k) + 1) (17)
Indeed, let a = qp + k, and assume that R and R * are two integers such that Γ a,k,k). Substituting for every row u = (u 1 , . . . , u a ) of Ψ and Φ row vector u = (u 1 , . . . , u a , a + 1, . . . , q), one gets a new pair of arrays that trivially belongs to Γ (R, R * , q, p, k). Hence, combining Theorem 1, inequality (17) and Property 3, one obtains Corollary 1.

(R, R * , a, k, k) = ∅. Let then (Ψ, Φ) ∈ Γ (R, R * ,
Table 5. Pairs of arrays that achieve γE(5, 3, 2) and γE [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF][START_REF] Escoffier | Differential approximation of MIN SAT, MAX SAT and related problems[END_REF][START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF].

Concluding Remarks

We make a few remarks as regards the combinatorial designs we introduced. When p = k, we think that 2/(T (q, k) + 1) is the exact value of γ(q, k, k). The question whether 2/(T (q, k) + 1) is optimal, though, still has to be settled. By contrast, when p > k, the only estimate of γ(q, p, k) we are aware of is the trivial lower bound of γ(qp + k, k, k). Yet, it the most likely holds given three integers k ≥ 2, p ≥ k and q > p that γ(q + 1, p + 1, k) > γ(q, p, k). Table 4, in which we indicate the value of γ(q, p, k) for a few triples (q, p, k), illustrates this fact quite well. Now, according to Lemma 1, these numbers provide for optimization CSPs with a bounded arity some lower bound on "how much we lose" on their optimum value when decreasing the size of their alphabet. This is a good motivation for studying families Γ (R, R * , q, p, k) of combinatorial designs in case when p > k.

Likewise, let k CSP(E q ) refer to the (generalized) optimization CSP over Z q where functions P i that occur in the constraints have arity at most k, are rational-valued, and satisfy: P i (y 1 + a, . . . , y ki + a) = P i (y 1 , . . . , y ki ), y∈ Z ki q , a ∈ Z q (18)

k CSP(E q ) notably covers the restriction of Lin-q to equations of the form α 1 y 1 + . . . + α k-1 y k-1 -(α 1 + . . . + α k-1 )y k ≡ α 0 mod q. Given an integer a, we denote by a the vector-of dimension that depends on the context-(a, . . . , a). On an instance I of k CSP(E q ), any constraint C i evaluates the same on any two entries x Ji and x Ji + a. The objective function v(I, .) similarly evaluates the same on any two entries x and x + a. This suggests to consider the slight relaxation Γ E (R, R * , q, p, k) of families Γ (R, R * , q, p, k) where Ψ and Φ have coefficients in Z q and, rather than requirements 2 and 3, satisfy the two conditions below: 2'. Φ r ∈ {(a, 1 + a, . . . , q -1 + a) | a ∈ Z q } holds for R * indices r ∈ [R]; 3'. for all J ⊆ [q] with |J| = k and all v ∈ {0} × Z k-1 q , Ψ J and Φ J coincide with a vector in {(v 1 + a, . . . , v k + a) | a ∈ Z q } on the same number of rows.

We define numbers γ E (q, p, k) just as the same as numbers γ(q, p, k). Table 5 pictures two such pairs of arrays, while Table 4 provides the value of γ E (q, p, k) for some triples (q, p, k). Using a similar argument as for the general case, it is not hard to see that, when restricting to input instances of k CSP(E q ), the reduction we proposed from k CSP-q to k CSP-p preserves the differential ratio up to a multiplicative factor of γ E (q, p, k). Notably, as γ E (q, 2, 2) = 1/q, q ∈ {3, 4, 5, 7}, it follows from [START_REF] Nesterov | Semidefinite relaxation and nonconvex quadratic optimization[END_REF] that when q ∈ {3, 4, 5, 7}, 2 CSP(E q ) is approximable within factor 0.429/q (and not only 0.429/(q -1) 2 ). Therefore, one also shall investigate families Γ E (R, R * , q, p, k) of combinatorial designs, starting with the case when p = k = 2.

Property 1 .

 1 , c ∈ N, b ≥ c (12) Numbers T (a, b) and S(a, b, c) satisfy the following: For all a, b ∈ N with a > b ≥ 1, the following equalities hold:

Property 2 .

 2 For all a, b, c ∈ N with b ≥ max{a, c}, S(a, b, c) equals b-a c .

Property 3 .

 3 For all a, b ∈ N with a > b ≥ 2, (ab/2) b is a proper lower bound for (T (a, b) + 1)/2.

CSPs All Are Approximable Within a Constant Differential Factor